[BOJ] 백준 8111 - 0과 1

문제 링크

www.acmicpc.net/problem/8111

8111번: 0과 1

 

풀이

1부터 시작해 0 또는 1을 붙여나가면서 $n$으로 나누어 떨어지는 수인지 확인합시다.

 

일반적으로 생각하면 수가 너무 크고, 경우의 수가 너무 많아 불가능합니다.

하지만 우리는 $n$으로 나누어 떨어지는지 여부만 알면 되기 때문에, 수 자체를 직접 저장하지 않고 그 수를 $n$으로 나눈 나머지 $r$만 저장해주면 됩니다.

어떤 수든 $(0 \leq r < n)$을 만족하므로 0, 1을 확장해가며 BFS를 돌려 정답을 찾을 수 있습니다.

 

$r$에 $0$을 붙이는 경우 $n$으로 나눈 나머지는 $(r$*$(10$ % $n))$%$n$,

$1$을 붙이는 경우 $n$으로 나눈 나머지는 $(r$*$(10$ % $n) + 1)$%$n$입니다.

 

어떤 값에서 어떤 값으로 전개됐는지를 저장하고, 이를 나머지 0에서부터 역순으로 추적하면 정답을 구할 수 있습니다.

 

 

만약 길이가 100자리를 넘는다면 따로 처리를 해줘야하지만, 그런 경우가 없다고 하니 따로 처리를 해주지 않았습니다.

정답 코드

#include <bits/stdc++.h>

#define TEST int _tt; cin >> _tt; while(_tt--)
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define mem(v, e) memset((v), (e), sizeof((v)))
using namespace std;
using pii = pair<int, int>;

pii par[22222];

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

    TEST {
        int n;
        cin >> n;
        mem(par, 0);
        queue<int> q;
        q.push(1);
        par[1] = {-1, -1};
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (now == 0) break;
            if (int next = now * 10 % n;!par[next].ft) {
                par[next] = {now, '0'};
                q.push(next);
            }
            if (int next = (now * 10 + 1) % n; !par[next].ft) {
                par[next] = {now, '1'};
                q.push(next);
            }
        }
        string ans;
        for (pii now = par[0]; now.ft != -1; now = par[now.ft]) {
            ans += now.sd;
        }
        ans += "1";
        reverse(all(ans));
        cout << ans << '\n';
    };
}