[백준] 8111번: 0과 1 - Python

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

0과 1

문제를 살펴보면, 간단한 BFS문제처럼 보인다. 예전에도 비슷한 문제를 푼 적이 있습니다. 

---

https://writedown-remain.tistory.com/63

백준 16953: A -> B.

간단한 BFS 문제입니다.

만들 수 있는 모든 경우의 수를 BFS로 탐색해 연산의 횟수를 출력하면 됩니다.

---

크게 다르지 않은 문제 형태입니다.

조건이 조금 다르긴 하지만요.

1로 시작해야 하고, 그 이후에 0과 1이 계속 붙어서 약간의 이진수처럼 숫자를 구성해야 합니다.

그리고 그 숫자는 입력받은 n으로 나눠저야 합니다.

따라서 밑의 코드처럼 매우 간단하게 풀 수 있을 줄 알았습니다. (간단했으면 플레티넘 문제가 아니겠지요?)

import sys
from collections import deque

add_num = ['0', '1']
ku_apple = "1"


def find_num_bfs(n):
    queue = deque([ku_apple])
    while queue:
        m_num = queue.popleft()
        if len(m_num) > 100:
            return 'BRAK'

        for d_num in add_num:
            n_num = m_num + d_num
            if int(n_num) % n == 0:
                return n_num
            else:
                queue.append(n_num)


t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(find_num_bfs(n))

코드 설명을 간단하게 하자면, 상하좌우 좌표를 모두 탐색하는 것과 비슷합니다.

백준 7576: 토마토에서는 상하좌우를 살펴야 하기 때문에 

dxy = [(1,0),(-1,0),(0,1),(0,-1)]

이렇게 dxy를 설정하고 for문을 사용해 상하좌우를 모두 살핍니다. 

이 문제에서도 다음에 올 수 있는 모든 수를 살핍니다.

add_num = ['0', '1'] # 그 다음 진행할 숫자를 만들기 위함

# 그 다음 숫자를 만듬.
for d_num in add_num:
    n_num = m_num + d_num
    if int(n_num) % n == 0:
        return n_num
    else:
        queue.append(n_num)

여기서 문제는 '모든 경우의 수가 들어간다'는 점입니다.

위 코드에서 n == 999인 순간.

제 로컬 환경에서 체감상 거의 30초 이상 기다려서 결과가 나왔던 것 같습니다.

 왜냐면, 

n ==9, output == 111111111111111111111111111

저 자릿수가 될 때까지 계속해서 0, 1을 붙여가면서 진행해야 하니 시간초과 or 메모리 초과가 나올게 뻔하죠?

역시 메모리 초과로 결과가 나오지 않습니다. 

그러면 여기서 생각을 해야 합니다. 

과연 메모리를 덜 사용할 방법이 어디 있을까?

---

 

여기서 메모리를 덜 사용한다는 말은 중복되는 수를 만든다는 말과 같은 말입니다.. 

중복된다? 중복되게 만들어야 한다? 보통 이럴 때 코딩 테스트 문제에서 쓰는 연산은 "나머지"입니다. 

(그냥 필자의 경험적인 추론입니다. 나머지 정말 좋아하는 것 같아요.)

n = 17일 때를 예시로 들어보겠습니다. 

뭔가 규칙성이 보이지 않나요?

100을 17로 나누면 나머지가 15인데 거기에 1이 붙는 순간! 나머지가 또 15입니다. 그다음에 1이 붙어도 또 1이 붙어도 계속 나머지가 15입니다. 그러면 100에 1을 붙이는 연산은 중복처리 할 수 있겠습니다.

그러면 나머지가 같은 연산끼리는 뭔가 규칙성이 있지 않을까요? (밑의 예시부터 (숫자, 나머지)로 보시면 편합니다.)

(10010, 14) -> (100100, 4), (100101, 5) 어디서 많이 보지 않았나요?

(1000, 14) -> (10000, 4), (10001, 5) 여기 있네요! 

이 문제가 플레티넘에 있는 이유였습니다. 나머지에 정답이 숨어있었습니다.

만약 나머지가 나오는 순서에도 규칙 있고, n보다는 클 수 없으니 나오는 모든 수를 저장하는 방식에서 0 ~ n-1까지만 저장하면 되는 방식으로 바뀌었네요. (메모리 문제 해결!)

그러면 위의 아이디어를 바탕으로 구현을 해보겠습니다.

import sys
from collections import deque

add_num = ['0', '1']
ku_apple = "1"


def find_num_bfs(n):
    queue = deque([(ku_apple, 1)])
    visited = set([1])  # 이미 확인한 나머지를 저장

    while queue:
        current_str, remainder = queue.popleft()

        if remainder == 0: # 이건 정답입니다.
            return current_str

        for d in add_num:
            new_str = current_str + d
            new_remainder = (remainder * 10 + int(d)) % n

            if new_remainder not in visited:
                queue.append((new_str, new_remainder))
                visited.add(new_remainder)

        if len(current_str) > 100:
            return 'BRAK'


t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(find_num_bfs(n))

 

휴 고생하셨습니다.