from collections import *
def check(nums):
one = 0
for i in range(1,len(nums)+1):
if nums[-i]=="0":
continue
if nums[-i]=="1":
one = 1
continue
return int(nums[-i]),i,one
return 0,0,0
def BFS():
dq = deque([1])
while dq:
x = dq.popleft()
nums = str(N*x)
if len(nums)>100:
continue
n1,i,one = check(nums)
if not i:
return nums
if one:
nums = nums[:-i+1]
if nums in memo:
continue
memo.add(nums)
for j in range(1,10):
if not (n*j+n1)%10 or (n*j+n1)%10==1:
dq.append(x+j*10**(i-c))
else:
for j in range(2,10):
if (n1*j)%10==1:
dq.append(x*j)
return "BRAK"
for _ in range(int(input())):
N = input()
while 1:
for c in range(1,len(N)+1):
if int(N[-c]):
n = int(N[-c])
break
if not n%2:
N = str(int(N)*5)
elif n == 5:
N = str(int(N)*2)
else:
break
N = int(N)
memo = set()
print(BFS())BFS로 어렵게 해결하였다.
아이디어는 이러하다. 어떤 수가 있을 때, 배수를 해서 0과 1로만 이루어지게 만들어주어야 한다. 따라서 이미 0인 부분과 1인 부분을 무시하면서 숫자를 더해나가는 방식으로 풀었다.
예를 들면 7이라는 숫자가 있다고 하자. 그럼 일단 7을 1로 만들어 주기 위해서 3을 곱한다. 그럼 21이 된다. 이때, 1은 유지한 채로 숫자 2를 1이나 0으로 바꾸어주어야 한다. 2에 7을 더해서 0이나 1을 만드는 방법은 2+28, 또는 2+49가 있다.
즉, 21+280 = 301과 21+490=511이 가능하다. 이 두 숫자를 dq에 넣고 위의 방법을 반복한다.
이 방법의 문제점은 위에 나왔다 싶이 매 경우에 가능한 가짓수가 2개씩 생기기 때문에 경우의 수가 지수적으로 늘어난다는 점이 있다. 따라서 이를 어떻게 해결할까 고민하다가 방문표시를 해주었다. 0과 1로 구성된 부분을 제외한 부분이 똑같은 경우는 더 이상 탐색하지 않는 것이다. 예를 들어 이전에 315110을 탐색했는데, 현재 31511001이라면, 0과 1을 제외한 나머지 부분인 315는 중복되므로, 탐색하지 않는 것이다.
이를 반복하다보면 최종 답을 구할 수 있게된다.
그런데 훨씬 간단한 풀이가 존재한다는 것을 알게되었다.
그냥 0과 1을 붙이면서 나머지에 대한 방문표시를 해주면 되는 것이었다.
이에 대한 코드는 아래와 같다.
import collections
for _ in range(int(input())):
N = int(input())
remain = [0]*N
dq = collections.deque(["0","1"])
while dq:
x = dq.popleft()
if not int(x)%N and int(x):
print(x)
break
if remain[int(x)%N]:
continue
remain[int(x)%N] = 1
dq.append(x+"1")
dq.append(x+"0")즉 숫자를 0, 1을 차례로 붙이면서 만약 현재 숫자의 나머지를 이미 방문했다면 continue하는 방식이다.
훨씬 코드도 깔끔하고 쉽게 구현할 수 있다.
참고로 BRAK은 출력할 일이 없다고 한다. 20000보다 작은 자연수에서는 무조건 구사과가 좋아하는 수가 존재한다고 한다.
오늘의 교훈) 다양한 풀이를 생각하자