1780 종이의 개수

#include <iostream>
using namespace std; 

int n;
int board[2188][2188]; 

int zero = 0, one = 0, mone = 0; 

bool check(int y, int x, int k) {
	int value = board[y][x];
	for(int i = y; i < y + k; i++)
		for (int j = x; j < x + k; j++) {
			if (board[i][j] != value)
				return false; 
		}
	return true; 
}

// (y, x)에서 시작해서 k만큼의 크기의 행렬을 검사하는 함수
void solve(int y, int x, int k) {
	if (k == 1 || check(y, x, k)) {
		if (board[y][x] == 0) zero++;
		else if (board[y][x] == 1) one++;
		else mone++; 
		return; 
	}
	int interval = k / 3; 
	for (int i = y; i <= y + k - interval; i += interval) {
		for (int j = x; j <= x + k - interval; j += interval) {
			solve(i, j, interval);
		}
	}
}

int main() {
	cin >> n; 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j]; 
	solve(0, 0, n); 
	cout << mone << endl << zero << endl << one << endl;
	return 0; 
}

시간복잡도는 9의 7승이다.

해설

void solve(int y, int x, int n) {
	if (same(y, x, n)) {
		cnt[a[y][x] + 1] += 1; 
		return;
	}
	int m = n / 3; 
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			solve(x + i * m, y + j * m, m);

내 풀이와 다른 점을 정리해보면,

(1) zero, one과 같이 변수로 저장하지 않고 cnt 배열에 값을 저장하여 더 깔끔하게 구현함

(2) interval 만큼 곱한 값을 solve의 인자에 넣어 호출함으로써, for문 안에서 직접 간격을 신경써주지 않았다.

11729 하노이의 탑 이동순서

(스스로 해결하지 못하였음)

해설

가장 크기가 큰 5번 원판에 집중하여 문제를 해결한다. 5번 원판을 3번 장대로 옮기기 위해서는 그 위의 1, 2, 3, 4 원판이 2로 이동해야한다.

1, 2, 3, 4 원판을 옮기기 위해서는 4번 원판 입장에서 1, 2, 3을 다른 장대로 옮겨야 한다는 특징이 있으므로, 재귀적으로 이를 해결할 수 있다.

solve(n, x, y) : n개의 원판을 x번 장대에서 y번 장대로 옮긴다.

위 예제에서 첫 호출은 solve(5, 1, 3) 이다. solve(4, 1, 2) → 5번 원판 이동 → solve(4, 2, 3) 이런 과정으로 풀 수 있는데, 이를 일반화 해보자.