[BOJ] 백준 8111, 8112. 0과 1 -2 (Platinum IV)

문제는 아래와 같다.

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

8112번: 0과 1 - 2

요약하자면, 100만 이하의 자연수 N의 배수 중 가장 작은 0과 1로만 이루어진 수를 출력하라는 문제이다. 단, 시작숫자는 0일 수 없다.

---

의식의 흐름 및 해설

모든 자연수의 배수는 0과 1로 표시할 수 있다는 점을 알고 있으면 좋다.

이산수학 시간에 배운다고 하는데, ps 덕분에 이산수학을 예습한 느낌 ㅎ...

아무튼 위 성질은 비둘기집의 원리로 증명할 수 있다.

 

자연수의 모든 배수는 0과 1로만 이루어진다는 것을 증명해보자.

 

자연수 N과, 1, 11, 111, 1111, ... , 111...11 (1이 N+1개) 와 같은 정수 N+1개가 있다고 하자.

이 수들을 N으로 나누면 나머지가 0~N-1까지 최대 N개의 나머지 종류의 개수가 나올 것이다.

따라서 N+1개의 정수 중 적어도 두 개 이상은 같은 나머지를 가지는 수가 존재한다.

같은 나머지를 가진 두 수의 차는 N으로 나누어떨어지고, 그 두 수의 차는 1과 0으로만 표현된다.

 

따라서 자연수 N은 길이가 N+1 이하인 1과 0으로만 이루어진 자연수의 최대공약수가 N임을 증명가능하다. 

 

자, 그럼 이제 BRAK이 나오는 경우는 존재하지 않는다는 걸 알았다.

그렇다고 이 수를 직접 숫자로 표현하자니 수가 굉장히 커서 c++로는 도저히 표현할 수가 없을 것 같다.

일일이 10, 11, 100, 101, ... 로 해서 길이가 100만까지인 수를 직접 만들어서 직접 N으로 나눠보는 건 절대 불가능할 것 같다.

 

다행히 수가 10, 11, 100, ... 과 같이 1과 0으로만 이루어져 있으므로 

자릿수가 늘어날 때마다 두갈래길만 주어지므로 bfs로 충분히 처리할 수 있을 듯하다.

백트래킹은 수가 너무 커서 불가능하다.

 

bfs로 x*10, x*10+1을 조사하여 큐에 담고, 만약 x가 N으로 나누어떨어진다면, 이 때가 답이므로 역추적을 이용해 출력해준다. 만약 큐에 string을 담는다면 8111번은 통과하지만, 8112번은 인자로 string을 일일이 O(string.length()) 만큼 소요돼 시간초과 또는 메모리초과를 받는다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1000002;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int t, N, trace[MAX];
char str[MAX];
string s;
vector<int> v;
bool visit[MAX];
void solve(int cur) {
	if (cur == -1)
		return;
	s += str[cur];
	solve(trace[cur]);
}
void bfs(int cur) {
	queue<int> q;
	q.push(1);
	visit[1] = true;
	trace[1] = -1;
	str[1] = '1';
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (!x) {
			solve(0);
		}
		for (int i = 0; i < 2; i++) {
			int nx = (x * 10 + i) % N;
			if (!visit[nx]) {
				visit[nx] = true;
				trace[nx] = x;
				str[nx] = (char)(i + '0');
				q.push(nx);
			}
		}
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> t;
	while (t--) {
		cin >> N;
		if (N == 1) {
			cout << 1 << "\n";
			continue;
		}
		fill(visit, visit + MAX, false);
		fill(trace, trace + MAX, -1);
		fill(str, str + MAX, '0');
		s.clear();
		bfs(N);
		reverse(all(s));
		cout << s << "\n";
	}
}

---

이 문제를 풀고나니

정수론, 수학적 증명을 공부해보고 싶어졌다.

물론 수학과의 엄밀한 증명은 싫고, ps의 수학적 감각을 길러보고 싶은 느낌이랄까...