[백준/BOJ] platinum5 - 8111번 0과 1 (Python)

▶8111 - 0과 1

백준 로

▶문제

폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

• 0과 1로만 이루어져 있어야 한다.
• 1이 적어도 하나 있어야 한다.
• 수의 길이가 100 이하이다.
• 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

 

▶출력

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

728x90

▶풀이

1과 0이 들어가는 모든 경우를 다 생각해서 mod 해주어도 된다.

근데 그렇게 하면 시간초과가 나서 다른 방법을 생각해 보았다.

 

일단 A mod B = C인 경우에서 곱하거나 더하는 경우를 고려해 보면

(A * D) mod B = (C * D) mod B

(A + D) mod B = (C + D) mod B

이렇게 나온다.

 

이 방법을 사용해 visit를 해주면 비슷한 경우를 반복하는 것을 제거할 수 있다.

 

visit의 사이즈는 n까지만 생각해 주면 된다.

나머지는 그 이상으로 올라가지 않기 때문이다.

 

bfs에서 queue에는 나머지(remind)와 현재 숫자(number)를 넣어 주었다.

숫자는 string으로 넣어준 이유는 최대길이 100을 판단해 줄 때 len으로 쉽게 하기 위해서이다.

 

나머지는 기본적인 bfs와 비슷하기 때문에 쉽게 풀 수 있다.

# A mod B = C
# (A × D) mod B = (C × D) mod B
# (A + D) mod B = (C + D) mod B
from collections import deque


def bfs():
    queue = deque()
    queue.append((1, '1'))
    visit[1] = 1

    while queue:
        remain, number = queue.popleft()
        if remain == 0:
            return number
        if len(number) > 100:
            return 'BRAK'

        if visit[(remain * 10) % n] == 0:
            visit[(remain * 10) % n] = 1
            queue.append(((remain * 10) % n, number + '0'))
        if visit[(remain * 10 + 1) % n] == 0:
            visit[(remain * 10 + 1) % n] = 1
            queue.append(((remain * 10 + 1) % n, number + '1'))

    return 'BRAK'


t = int(input())
answer = []

for _ in range(t):
    n = int(input())
    visit = [0 for _ in range(n + 1)]
    answer.append(bfs())

for ans in answer:
    print(ans)

오랜만에 플레티넘 풀고 싶어서 쉬운 문제를 고르고 골랐다.

쉬워 보였던 플레티넘을 풀다가 두 문제나 거르고, 세 번째에 쉬운 플레티넘을 찾았다.

 

이렇게 쉬운 플레티넘 문제를 찾으면 쉽게 solved.ac 티어를 올릴 수 있다.