8111 0과 1

1. 문제

2. 코드

#include <stdio.h>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define _CRT_SECURE_NO_WARNINGS
 
using namespace std;
//arr.first arr.second
pair<int,char> arr[20001];
int n;
bool visit[20001];
 
void bfs(void);
void print(int n);
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        
        if (n == 1) {
            cout << 1 << endl;
            continue;
        }
        bfs();
        print(0);
        cout << endl;
    }
}
 
void bfs(void) {
 
    memset(visit, false, sizeof(visit));
    queue<int> q;
    visit[1] = true;
    q.push(1);
    arr[1].first = -1;
    arr[1].second = '1';
    
    while (!q.empty()) {
        int temp = q.front();
        q.pop();
        int p[2];
        p[0] = (temp * 10) % n;
        p[1] = (p[0] + 1) % n;
 
        for (int i = 0; i < 2; i++) {
            if (!visit[p[i]]) {
                arr[p[i]].first = temp;
                arr[p[i]].second = i + '0';
                if (!p[i])
                    return;
                visit[p[i]] = true;
                q.push(p[i]);
            }
        }
    }
}
 
void print(int n) {
    if (n == -1)
        return;
    print(arr[n].first);
    cout << arr[n].second;
}

3. 후기

이 문제는 처음에 1로 시작하고 0과 1을 뒤에 붙인 즉, 10%n 과 11%n을 큐에 넣어가며 배열에 저장하는데 하나는 10%n가 만들어지기 전의 숫자 넣고 하나는 뒤에 붙인 숫자를 문자로 넣어준다. 10%n를 배열의 인덱스로 하여 넣는다. 나중에 출력할 때 자식의 부모를 따라가면서 반대로 출력할 수 있다. 

arr[1].first = -1

arr[1].second = '1'

arr[10].first = 1

arr[10].second = '0'

arr[11].first = 1

arr[11].second = '1'

arr[15].first = 10

arr[15].second = '0'

arr[16].first = 10

arr[16].second = '1'

arr[17].first = 15

arr[17].second = '0'

출처 - https://jaimemin.tistory.com/791