취미로 코딩하기

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

이번에 볼 문제는 백준 10435번 문제인 만칼라이다.
문제는 아래 링크를 확인하자.

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

"구슬이 총 N개일 때 승리하는 게임판은 항상 유일하다"는 주어진 내용을 눈여겨보자. 이 내용을 먼저 증명해보자.

증명은 수학적 귀납법을 이용할 것이다. N=1일 때 승리하는 게임판은 유일함은 자명하므로 우리의 목적은 "구슬이 N개일 때 승리하는 게임판이 유일하면 N+1개일 때 승리하는 게임판 또한 유일함"을 증명하는 것이다.

먼저, 가능한 모든 조작은 Roumba에 있지 않은 구슬의 개수를 항상 1씩 줄여나간다는 점을 관찰하자. 또한 Roumba에 있는 구슬은 더 이상 조작하지 않으므로 없는 것과 같이 생각할 수 있다는 점을 관찰하자. 이러한 관찰을 이용하면 구슬이 N+1개 있을 때 한 번의 조작을 하면 (Roumba에 있지 않은 구슬만을 고려하면) N개의 구슬이 있는 상태로 바뀐다고 생각할 수 있다. 한편 가정에 따라 구슬이 N개일 때 승리하는 게임판은 유일하므로, 이 N개의 구슬이 있는 상태에 도달할 수 있는 N+1개의 구슬의 배치를 모두 찾아보는 것만으로 N+1개의 구슬로 이루어진 모든 승리하는 게임판을 찾을 수 있게 된다.

N+1개의 구슬이 배치되어있을 때 k번 칸을 선택해 N개의 구슬이 배치되어있는 것과 같은 형태로 만들었다면, N개의 구슬이 배치되어있을 때 k번 칸에는 구슬이 0개 있어야 함을 알 수 있다. 또한 k번 칸을 조작했다면 1...k-1번 칸에는 구슬이 항상 존재하게 됨을 알 수 있다. 따라서 N개의 구슬이 배치되어있는 모습을 기준으로 "양의 정수 k에 대하여 구슬이 0개 존재하는 가장 작은 k"에 해당하는 칸을 N+1개의 구슬이 배치되어있을 때 조작하는 것 외에는 N+1개의 구슬이 놓여있는 게임판을 (유일한) N개의 구슬이 배치되어있는 형태로 만들 수 없음을 알 수 있다. 이것으로 증명을 마친다.

위 증명으로부터 "가능한 N개의 구슬 배치로부터 N+1개의 구슬 배치를 구성해내는 알고리즘"을 구성해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int P;
int ans[2501][101];

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

	ans[1][0] = ans[1][1] = 1;
	for (int i = 1; i < 2500; i++) {
		int k = 1;
		while (ans[i][k]) k++;
		for (int j = 1; j < k; j++) ans[i + 1][j] = ans[i][j] - 1;
		ans[i + 1][0] = ans[i + 1][k] = k;
		for (int j = k + 1; j < 101; j++) {
			ans[i + 1][j] = ans[i][j];
			if (ans[i][j]) ans[i + 1][0] = j;
		}
	}

	cin >> P;
	while (P--) {
		int T, N; cin >> T >> N;
		int& cnt = ans[N][0];
		cout << T << ' ' << cnt << '\n';
		for (int j = 1; j <= cnt; j++) {
			cout << ans[N][j] << ' ';
			if (j % 10 < 1) cout << '\n';
		}

		if (cnt % 10) cout << '\n';
	}
}