[백준/8111] 0과 1 (Python)

Problem : https://www.acmicpc.net/problem/8111

8111번: 0과 1

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:17:51

 

---

 

문제 설명

 

 

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

 

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

 

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

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

 

 

입력 및 출력

 

입력

 

첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다.
둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

 

출력

 

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

 

입력 예시

 

6
17
11011
17
999
125
173

 

출력 예시

 

11101
11011
11101
111111111111111111111111111
1000
1011001101

 

 

---

 

풀이

 

꽤 흥미로웠던 문제. 잘 숨겨둔 그래프 탐색 문제였다.

 

관점을 바꾸어, 1부터 시작해 뒤에 0이나 1을 붙이는 식으로 그래프 탐색을 진행한다고 생각하자. 이는 1, 2, 4번 조건을 동시에 충족시킨다(1로 시작하지 않고, 0 혹은 1로만 구성되어 있으며, 최소 1개의 1 - 맨 앞자리 - 을 포함). 

 

다음에 고려해야 할 점은 경우의 수이다. raw하게 모든 경우를 저장한다고 가정하면 n자리일 때 총 2^n자리를 포함하게 된다. 하지만 우리는 N으로 나눠지는 수를 포함한다. 즉 N의 나머지의 경우의 수, 최대 N가지 경우만을 저장하면 된다. 1부터 시작해 뒤에 0이나 1을 붙이는 식은 바꾸어 말하면 앞선 수에 10을 곱하고 0 또는 1을 더함을 의미한다. 모듈러 연산은 덧셈과 곱셈에 대해 교환 및 결합법칙이 적용되므로 경우의 수를 앞선 나머지 수로만 고려하면 된다. 여기에 백트래킹을 위해 (이전의 나머지, 이전에 더한 수 - 0 또는 1)을 저장하도록 하였다. 나머지가 0이 되는 순간 백트래킹으로 결과를 출력하면 된다.

 

풀이 코드

from collections import deque

def solve() :
  N = int(input())
  visited = [[(-1, -1)]*N for _ in range(101)]
  visited[1][1%N] = (1, N)
  q = deque([(1, 1%N)])

  while q :
    length, left = q.popleft()
    if not left :
      result = ''
      for i in range(length, 0, -1) :
        val, left = visited[i][left]
        result += str(val)
      print(result[::-1])
      return
    if length == 100 :
      continue

    for n in range(2) :
      new_left = (left * 10 + n) % N
      if visited[length+1][new_left][0] == -1 :
        visited[length+1][new_left] = (n, left)
        q.append((length+1, new_left))
  return

for _ in range(int(input())) :
  solve()

풀이 완료!