[C++] 백준 8111 : 0과 1

1. 문제 출처

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

8111번: 0과 1

 

 

 

 

2. 문제 접근

$N$이 주어졌을 때, 100 자릿수 이하인 $N$의 배수를 구하는 데에는 시간도 매우 많이 걸리고, 해당 수를 담을 자료형도 long long으로 부족하기 때문에 string연산으로 해결을 해줘야 한다. 따라서 반대로, 1과 0으로 이루어진 수들을 작은 자리 수부터 생성을 하고, 그 수가 $N$의 배수인지 ($N$)으로 나눈 나머지가 0인지) 확인만 해주면 되었다.

 

 

 

 

1과 0으로 이루어진 100자리의 수 역시 매우 큰 수 이므로, 나머지 연산을 활용해야만 했다. 1과 0으로 이루어진 수를 생성하기 위해서 BFS를 사용하여 1 > 10, 11 > 100, 101, 110, 111 > ... 과 같이 생성을 하였고, 생성이 된 수마다 앞에서 말한 나머지 연산을 사용하였다. 이렇게 생성이 된 수가 0이 되었다면, 그 수는 입력으로 주어진 $N$으로 나누어 떨어지므로 해당 수에 대한 정답을 출력하면 되었다.

 

 

 

 

지속적으로 나머지 연산을 진행하기 때문에, 원래의 값도 같이 저장하게 pair<int, string>으로 선언을 진행하였다.

 

 

 

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int testcase, n, nx[2];
bool visited[20001];
string ns[2];

void bfs() {
    queue<pair<int, string>> q;
    q.push({1, "1"});
    visited[1] = true;
    
    while (!q.empty()) {
        int x = q.front().first;
        string s = q.front().second;
        q.pop();

        if (x == 0) {
            cout << s << "\n";
            return;
        }

        nx[0] = (x * 10) % n;
        ns[0] = s + "0";

        nx[1] = (x * 10 + 1) % n;
        ns[1] = s + "1";

        for (int i = 0; i < 2; ++i) {
            if (visited[nx[i]]) continue;
            visited[nx[i]] = true;
            q.push({nx[i], ns[i]});
        }
    }

    cout << "BRAK\n";
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> testcase;
    while(testcase--) {
        cin >> n;
        memset(visited, false, sizeof(visited));
        if (n == 1) cout << "1\n";
        else bfs();
    }

    return 0;
}