1. 문제
폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.
- 0과 1로만 이루어져 있어야 한다.
- 1이 적어도 하나 있어야 한다.
- 수의 길이가 100 이하이다.
- 수가 0으로 시작하지 않는다.
- 예를 들어, 101은 구사과가 좋아하는 수이다.
자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다.
둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.
3. 출력
각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.
4. 예제 입력 / 출력
6
17
11011
17
999
125
173
11101
11011
11101
111111111111111111111111111
1000
1011001101
5. 풀이 과정
from collections import deque
def bfs(num):
queue = deque([1])
while queue:
cur = queue.popleft()
if len(str(cur)) > 100:
return 'BRAK'
if cur % num == 0:
return cur
queue.append(cur * 10)
queue.append(cur * 10 + 1)
return 'BRAK'
n = int(input())
for _ in range(n):
print(bfs(int(input())))처음에는 단순히 1 부터 시작해 BFS를 통해 0 또는 1을 붙여 그 수가 배수인지 확인하는 방식으로 코드를 짰다. 하지만 수가 100자리까지 갈 수 있고 (스택 오버플로우 발생) 이에 따른 경우의 수도 2^100이나 되기 때문에 단순한 BFS로는 풀 수 없었다.
이를 해결할 방법은 혼자 생각해서는 찾지 못했고 검색을 해본 결과 모듈러 연산을 사용해 수의 범위를 줄이는 것이 핵심이였다.
A mod B = C 이고 임의의 수를 D라 한다면
(A × D) mod B = (C × D) mod B
(A + D) mod B = (C + D) mod B
이므로 나머지에 임의의 숫자를 더해주거나 곱해주는 것은 몫에 임의의 숫자를 더해주거나 곱해주는 것과 같기 때문에 문제에 적용해 보면 나머지에 0과 1을 덧붙인 후 다시 n으로 나누면 몫에 0과 1을 덧붙여 나눈것과 동일한 결과이다. 이를 통해 오버플로우를 방지해줄 수 있다.
코드를 작성해보면 다음과 같다.
from collections import deque
def bfs(num):
# 문자형으로 원래 숫자도 저장
queue = deque([(1, '1')])
visited = [False] * 20001
visited[1] = True
while queue:
cur_num, cur_str = queue.popleft()
if cur_num == 0:
return cur_str
if len(cur_str) > 100:
return 'BRAK'
# x modular n은 (x modular n) modular n과 같음
if not visited[(cur_num * 10) % num]:
visited[(cur_num * 10) % num] = True
queue.append(((cur_num * 10) % num, cur_str + '0'))
if not visited[(cur_num * 10 + 1) % num]:
visited[(cur_num * 10 + 1) % num] = True
queue.append(((cur_num * 10 + 1) % num, cur_str + '1'))
return 'BRAK'
n = int(input())
for _ in range(n):
print(bfs(int(input())))이 방식을 통해 최대 2^100나 되는 경우의 수를 19999가지의 경우의 수까지 줄일 수 있고 또한, 이미 방문한 나머지는 같은 연산을 다시 할 필요가 없기 때문에 넘기면서 많은 시간을 절약할 수 있다.
6. 문제 링크
