[백준-8111] 0과 1

시간 제한은 1초에 테스크 케이스의 개수가 1000개이니 각 테스트 케이스마다 최소 10만 이내의 복잡도로 끝내야 하는 문제이다. 이때 수가 20000까지의 수이기 때문에 반복문 2개를 놓는순간 제한에 걸리게 된다.

이 문제는 조건과 나머지의 규칙을 통해 풀 수 있다. 다음 식들을 쭉보자

• 10 = (1 * 7) + 3
• 100 = (10 * 7) + 30
• 101 = (10 * 7) + 31
• ......

이 식들을 보았을 때 나누게 되는 수가 10곱만큼 늘어나게 되면 나머지 역시 10곱만큼 늘어나게 된다. 또한 나누게 되는 수가 1만큼 늘어나게 되면 나머지 역시 1만큼 늘어나게 된다. 이를 이용해서 string, int 값을 queue 에 넣어가면서 나머지가 0이 될 때까지 탐색을 돌릴 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int check[20001];

string bfs(int n) {
    queue<pair<string,int>> q;
    q.push({ "1", 1 });
    // 첫번째 나머지
    check[1] = 1;

    while (!q.empty()) {
        string cstr = q.front().first;
        int cnum = q.front().second;
        q.pop();
        if (cnum == 0) return cstr;
        for (int i = 0; i < 2; i++) {
            // i=0 : 10을 곱한다
            // i=1 : 10을 곱한 뒤 1을 더한다.
            int tx = (cnum * 10 + i) % n;
            if (check[tx]) continue;
            check[tx] = 1;
            q.push({ cstr + to_string(i), tx });
        }
    }
    return "";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    // 100 101 110 111 
    int n;
    for (int i = 0; i < t; i++) {
        memset(check, 0, sizeof(check));
        cin >> n;
        // 각 테케마다 10만의 복잡도 안으로 끝내야 한다.
        string ans = bfs(n);
        if (ans.empty()) cout << "BRAK" << "\n";
        else cout << ans << "\n";
    }

    return 0;
}

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

8111번: 0과 1