개발 블로그

문제 링크 : www.acmicpc.net/problem/8111

문제

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

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

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

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

입력

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

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

출력

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

접근 방법

N의 배수가 최대 100자리 까지 나올 수 있기 때문에 무작정 0과 1을 붙여가면서 N으로 나눠지는지 확인하면 안 된다. (오버플로우) 

어떤 수 x 가 N의 배수인지 확인하려면 (x mod N) 이 0인지 확인할 수도 있겠지만 x가 계속 커지는 걸 방지하기 위해 (x mod N) mod N이 0인지 확인하면 된다. modular 연산의 성질에 의해   (x mod N) 는 (x mod N) mod N와 같기 때문이다. 

그래서 x 대신 "현재의 수 cur에 0또는 1을 붙이고 N으로 나눈 나머지"를 고려하면 된다.  

cur = 1이라면 node[0]은 10%N. node[1] = 11%N이 된다. 

//자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;

그럼 어떻게 원래의 수를 기억할것인가?

매 depth 마다 0을 붙였는지 1을 붙였는지를 char 형으로 저장한 뒤에, depth가 마지막까지 내려왔을 때 거꾸로 올라가면서 어떤 수를 붙여왔는지 출력하면 된다. 

그럴려면 현재 노드에서 부모 노드를 타고 거꾸로 올라가려면 해당 노드의 부모 노드 번호를 알아야한다. 

arr[자식idx].first 에는 idx번째 자식노드의 부모 노드 번호를 저장하고,

arr[자식idx].second 에는 해당 depth에서 붙인 숫자를 char 형으로 저장한다. ('0' or '1')

다 저장하고 마지막에 0번째 자식부터 재귀 함수를 통해 거꾸로 올라가면서 arr[].second 를 출력한다. 이때, 0번째 자식부터 시작하는 이유는 (x mod N) mod N이 0이 되면서 그 0을 arr[]의 idx로 지정해 정보를 저장한 뒤, BFS() 함수를 종료했기 때문이다. 

//
//  BFS_BOJ8111_0과1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/02. 05:27~06:10 / 06:24 / 06:40
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;
int N;
int visited[20001] = {0};
pair<int, char> arr[20001];

void BFS(){
    memset(visited, 0, sizeof(visited));
    queue<int> que;
    que.push(1);        //첫 글자는 0 안 됨
    
    //가장 첫 루트 노드
    arr[1].first = -1;   //부모 노드 번호 표시 (부모가 -1이면 루트 노드인 것)
    arr[1].second = '1'; //N의 배수는 1부터 시작하므로

    visited[1] = 1;
    
    
    while(!que.empty()){
        
        int cur = que.front();
        que.pop();
        
        
        //자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;
        
        for(int i = 0; i<2; i++){
            if(visited[node[i]]==1) continue;
            
            arr[node[i]].first = cur;   //node[i]의 부모 노드는 cur
            arr[node[i]].second = i + '0';      // 현재 수에서 어떤 수를 덧붙였는지 저장, i는 0또는 1인 정수. 여기에 '0' 더해서 char 형으로 변환
            
            if(node[i]==0) return;      //N으로 나눈 나머지가 0이므로 N의 배수 찾은 것
            
            visited[node[i]] = 1;       //방문했음을 표시
            que.push(node[i]);
            
            
        }
        
        
    }
    
}

void printReverse(int parent){
    if(parent==-1) return;      //부모 노드가 -1이면 루트 노드
    
    printReverse(arr[parent].first);
    cout << arr[parent].second;
    
}


int main(){
    
    
    int T; cin >> T;
    
    for(int test_case = 1; test_case<=T; test_case++){
        
         cin >> N;
        if(N==1) {
            cout << 1 << endl;      //1의 배수는 1이므로 바로 출력
            continue;
        }
        
        BFS();
        printReverse(0);            //arr[0] 부터 거꾸로 타고 올라감. 0부터 시작하는 이유는 N의 배수가 되면서 나머지가 0이 됐고 이를 인덱스로 해서 저장했기 때문에
        cout << endl;
        
        
    }
    
    return 0;
}

참고 : jaimemin.tistory.com/791