0과 1( BOJ 8111 )

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

8111번: 0과 1

 

문제 파악하기

0과 1로 이루어졌으며 길이가 100 이하인 숫자 중 N의 배수를 구하는 문제입니다. 최대 길이가 정해져있지만 모든 경우를 확인하기에는 2¹⁰⁰이라는 경우의 수는 너무 많습니다. 그렇기에 굳이 확인할 필요가 없는 숫자는 확인하지 않아도 되며, 이 때 사용할 수 있는 도구는 바로 나머지 연산입니다.

 

문제 해결하기

나머지 연산을 어떻게 활용하면 불필요한 탐색을 제거할 수 있을까요? 우리가 사용하는 숫자는 0과 1이며 나누는 숫자는 항상 N입니다. 이런 상황에서 우리가 만든 숫자를 N으로 나눈 나머지가 이미 나온 적이 있다면 그 이후의 탐색은 무의미합니다. 이미 다른 숫자가 탐색을 하고 있다는 의미이기 때문입니다. 이는 비둘기집 원리로도 설명할 수 있으며 우리는 이 점을 활용하여 배열을 선언하고 만들어진 모든 숫자들의 나머지를 구합니다. 그리고 한 번이라도 나온 적이 있는 나머지라면 해당 숫자의 탐색을 멈춥니다. 이렇게 탐색의 범위를 나머지를 활용하여 줄이면 충분히 빠르게 0과 1로 N의 배수를 만들 수 있는지 여부를 구할 수 있습니다.

 

기본적인 탐색은 큐를 활용한 BFS로 진행할 수 있습니다. 0과 1를 번갈아가면 사용하면서 숫자를 넓게 탐색하는 것이 문제를 해결하기 훨씬 유리하기 때문입니다. 큐에는 { 현재 숫자(나머지), 길이 } 를 저장한 다음 [ (현재숫자*10)%N ] 과 [ (현재숫자*10+1)%N ] 2가지 경우를 각각 살펴보면서 큐에 저장할지 여부를 결정할 수 있습니다. 이렇게 탐색을 쭉 진행하면서 N에 나누어떨어지거나 길이가 100이 되는 순간 탐색을 종료하면 됩니다.

 

그렇다면 실제 어떤 숫자가 N의 배수인지 역추적할 수는 없을까요? 이 경우에는 배열을 활용할 수 있습니다. 배열은 현재 숫자(나머지 값)과 길이로 만들 수 있습니다. 그리고 만든 2차원 배열에는 항상 이전 나머지 값을 저장하면 정답을 구한 순간 역추적이 가능합니다. 만약 다음 상태 값은 nxt이며 배열을 route[nxt][cnt] 라고 가정해보겠습니다. 그럼 route[nxt][cnt]에는 현재 값인 cur을 저장하면 탐색이 끝난 다음 조건문을 통해 역추적을 할 수 있습니다. 이렇게 cnt가 남아있는 동안 역추적을 한 다음 결괏값을 반환하면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <iostream>
#import <string.h>
#import <utility>
#import <queue>
#define NMAX 20010
#define PAIR pair<int, int>
using namespace std;
 
int T, N;
int mod[NMAX];
int route[NMAX][105];
 
string ret;
int cur, nxt, cnt;
queue< PAIR > q;
 
string getNum(int cur, int cnt) {
    string ret="";
 
    while(cnt > 0) {
        // 이전 나머지 값과 현재 나머지 값을 비교해 0/1 판단하기
        if((route[cur][cnt]*10)%N == cur) ret = "0" + ret;
        else ret = "1" + ret;
 
        cur = route[cur][cnt];
        cnt--;
    }
 
    return ret;
}
 
int main() {
    cin >> T;
    while(T--) {
        // init
        ret = "-1";
        memset(mod, 0, sizeof(mod));
        memset(route, 0, sizeof(route));
        while(!q.empty()) q.pop();
 
        // input
        cin >> N;
 
        // BFS
        route[1][1] = -1;
        q.push({1, 1});
        while(!q.empty()) {
            cur = q.front().first;
            cnt = q.front().second;
            q.pop();
 
            if(cur%N == 0) {
                ret = getNum(cur, cnt);
                break;
            }
            else if(cnt == 100) break;
            else {
                // 0과 1 한번씩 넣기
                for(int k=0;k<2;k++) {
                    nxt = (cur*10 + k)%N;
 
                    if(mod[nxt]) continue;
                    else {
                        mod[nxt] = 1;
                        route[nxt][cnt+1] = cur;
                        q.push({nxt, cnt+1});
                    }
                }
            }
        }
 
        if(ret == "-1") cout << "BRAK\n";
        else cout << ret << "\n";
    }
}

후기

너비 우선 탐색과 수학을 적절하게 버부린 문제입니다. 역추적 하는 과정이 살짝 난이도를 올려주는 듯 합니다. 오래 전에 나온 문제라서 클래식한 느낌이 있지만 너비 우선 탐색을 연습하는 사람에는 적절한 문제라고 생각합니다.