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

문제

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

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

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

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

입력

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

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

출력

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

풀이

100자리 이하의 0과 1로만 이루어진 수 중 $N$의 배수를 아무거나 출력하는 문제이다. $2^{100}$개를 전부 확인할 수는 없으므로 탐색 범위를 줄이는 것이 목표이다.

0과 1로만 이루어진 수의 맨 뒤에 0 또는 1을 붙이면 다시 그러한 수를 얻을 수 있다. 즉 0과 1로만 이루어진 수 $x$에 대해 $10x$와 $10x+1$ 또한 그러하다. 1을 시작으로 $10x$와 $10x+1$을 반복하면 0과 1로만 이루어진 수를 전부 얻을 수 있다.

어떤 수 $x$와 $y$가 $x \mod N = y \mod N$을 만족하면 $10x \mod N = 10y \mod N$이고 $10x+1 \mod N = 10y+1 \mod N$이므로 둘은 같은 결과를 낸다. 즉, 나머지가 같은 수는 어차피 같은 결과를 내므로 전부 고려하지 않아도 된다. 따라서 모든 과정에서 $N$으로 나눈 나머지만 사용하여 탐색할 수 있다. 1을 큐에 넣고 $10x$와 $10x+1$의 나머지를 다시 큐에 넣는 BFS를 진행하면 된다.

다만 나머지만 고려할 시 원래 숫자가 무엇인지 추적할 수 없으므로, 원래 숫자를 문자열로 함께 큐에 넣도록 하였다.

코드

c++

#include <bits/stdc++.h>
using namespace std;
bool vstd[20001];

string bfs(int n){
    deque<pair<int, string>> q;
    q.push_back({1, "1"});
    vstd[1] = true;
    int f; string s;
    while (!q.empty()){
        f = q.front().first;
        s = q.front().second;
        if (f == 0) return s;
        q.pop_front();
        if (s.length() >= 100) return "BRAK";
        if (!vstd[(f * 10) % n]) q.push_back(make_pair((f * 10) % n, s + "0"));
        if (!vstd[(f * 10 + 1) % n]) q.push_back(make_pair((f * 10 + 1) % n, s + "1"));
        vstd[(f * 10) % n] = true;
        vstd[(f * 10 + 1) % n] = true;
    }
    return "BRAK";
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n, T; cin >> T;
    for (int _T = 0; _T < T; _T++){
        memset(vstd, false, sizeof(vstd));
        cin >> n; cout << bfs(n) << "\n";
    }
}

python

for _ in range(int(input())):
    n = int(input())
    v, q = [0] * n, [[1, "1"]]
    while q:
        if q[0][0] == 0:
            print(q[0][1])
            break
        if len(q[0][1]) >= 100:
            print("BRAK")
            break
        if not v[(q[0][0] * 10) % n]: q.append([(q[0][0] * 10) % n, q[0][1] + "0"])
        if not v[(q[0][0] * 10 + 1) % n]: q.append([(q[0][0] * 10 + 1) % n, q[0][1] + "1"])
        v[(q[0][0] * 10) % n], v[(q[0][0] * 10 + 1) % n] = 1, 1
        q = q[1:]
    else:
        print("BRAK")