BOJ-8111 0과1

필요한 지식

1. 수학

2. BFS

접근

• 수의 길이가 100이하 까지 이다. 수를 표현할 다른방법이 필요하다.

• String 형식으로 수를 표현한다.

• 입력받은 N의 배수 이면서 조건들을 만족해야한다.

• 단순히 N의 배수를 계속 곱하다 보면 자료형의 범위를 초과 하므로 다른 방법이 필요하다.

• N의 배수를 구해 줄 때 모듈러 연산을 해주면서 자료형의 범위를 넘지 않게 처리해 준다.

• BFS로 pair<int,string> : 모듈러 연산이 된 값, 모듈러 연산을 하지 않은 문자열로 표현된 숫자. 형태의 노드를 넣고 가능한 경우들을 봐준다.

• 첫 시작은 {1,"1"}의 형태로 시작되며, 뒤에 0이붙는 경우 1이 붙는 경우를 봐주며 진행한다.

코드(C++)

#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0), cin.tie(), cout.tie();
using namespace std;
int chk[20001];

queue<pair<int, string>>q;

string bfs(int x) {
    q.push({ 1,"1" });
    chk[1] = 1;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (cur.first == 0) return cur.second;
        for (int k = 0; k <= 1; k++) {
            int tmp = (cur.first * 10 + k) % x;

            if (!chk[tmp]) {
                chk[tmp] = 1;
                if (k == 0) q.push({ tmp,cur.second + "0" });
                else q.push({ tmp,cur.second + "1" });
            }
        }
    }
    return "BRAK";
}
int main() {
    FIO;
    int t; cin >> t;
    for (int i = 0; i < t; i++) {
        int n; cin >> n;
        memset(chk, 0, sizeof(chk));
        cout << bfs(n) << "\n";
        while (!q.empty()) q.pop();
    }
    return 0;
}

결과