취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8112번 문제인 0과 1 - 2이다.
문제는 아래 링크를 확인하자.

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

8111번 문제에서 T가 커지고 N이 작아진 문제이다.

8111번 풀이글에서의 풀이를 그대로 쓰면 긴 문자열을 계속 복사하는 데에는 문자열의 길이만큼의 시간복잡도가 필요하여 시간초과가 나므로 그 대신 백트래킹을 통해 답안을 구해주자.

각 "나머지" 별로, 그 나머지를 갖게 하는 최소의 숫자는 BFS의 탐색순서로 만들어진 BFS 트리를 따라 거꾸로 가는 것이므로 이를 이용해 백트래킹이 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int ans[1000001];
int visited[1000001];
int parent[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	while (N--) {
		memset(visited, 0, sizeof(visited));
		int x; cin >> x;
		if (x == 1) cout << 1 << '\n';
		else {
			queue<int> que;
			ans[1] = 1;
			que.push(1);
			while (!que.empty()) {
				int r = que.front(); que.pop();
				if (r == 0) {
					vector<int> vec;
					int temp = 0;
					while (temp != 1) {
						vec.emplace_back(ans[temp]);
						temp = parent[temp];
					}
					vec.emplace_back(1);
					if (vec.size() <= 100) {
						for (auto iter = vec.rbegin(); iter != vec.rend(); iter++) cout << *iter;
						cout << '\n';
					}
					else cout << "BRAK\n";
					break;
				}
				int rr = r * 10 % x;
				if (!visited[rr]) {
					visited[rr] = 1;
					ans[rr] = 0;
					parent[rr] = r;
					que.push(rr);
				}
				rr = (r * 10 + 1) % x;
				if (!visited[rr]) {
					visited[rr] = 1;
					ans[rr] = 1;
					parent[rr] = r;
					que.push(rr);
				}
			}
			if (!visited[0]) cout << "BRAK\n";
		}
	}
}