[알고리즘] 백준 1309번: 동물원 (C++), 너무 아쉽다

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

1309번: 동물원

이번 문제는 개인적으로 너무 아쉬웠다. 각 항의 관계성까지 파악하고, 이런 비슷한 문제가 있었던 걸 기억하여 비슷하게 구현해보려 했는데 구현이 되지 않아서 거의 90%까지 왔지만 결론적으로는 풀지 못 한 문제다.

 

[기억했던 비슷한 문제]

https://draw-code-boy.tistory.com/51?category=963936 

[알고리즘] 백준 1149번: RGB거리 (C++), 점화식...

 

[각 항들 사이의 관계]

각 항의 관계는 다음과 같다.

사자가 있는 칸에 동그라미를 친 것이다.

사자가 윗 칸에 있다면 다음 칸에는 없거나 대각선에 있어야 한다.

아랫 칸에 있을 때에도 마찬가지의 이유이고, 현재 칸에 없다면 어느 칸에 있든 없든 상관이 없다.

 

[비슷한 문제가 떠올랐었다]

풀이가 비슷하다기보다는 상황이 비슷했어서 이 문제도 마찬가지로 행이 3이거나 열을 3으로 주어서 2차원 배열로 풀 수 있을 거 같은 느낌이 들었으나 정작 중요한 점화식을 세우지 못했다.

 

참고했던 코드를 살펴보자.

(https://guiyum.tistory.com/21)

#include <iostream>
using namespace std;
#define MOD 9901

int cache[100001][3] = { 0, };

int main() {
	int n;
	cin >> n;
	cache[1][0] = 1; // 윗 칸에 사자가 있는 경우
	cache[1][1] = 1; // 아랫 칸에 사자가 있는 경우
	cache[1][2] = 1; // 둘 다 빈 칸인 경우
	for (int i = 2; i <= n; i++) {
		cache[i][0] = (cache[i - 1][1] + cache[i - 1][2]) % MOD;
		cache[i][1] = (cache[i - 1][0] + cache[i - 1][2]) % MOD;
		cache[i][2] = (cache[i - 1][0] + cache[i - 1][1] + cache[i - 1][2]) % MOD;
	}

	cout << (cache[n][0] + cache[n][1] + cache[n][2]) % MOD;
	return 0;
}

 

코드는 이렇게 말한다.

'지금 현재 항의 이전 항이 무엇이었는지에 따라 전의 경우의 수들을 더하라.'

나와 관점이 달랐던 거 같다.

나는 이전 항을 이용하여 다음 항(현재 항)을 구하려 했었기에 점화식도 나오지 않았던 거 같다.

또다시 강조를 해야 하는 내용이다. '현재 항은 어떻게 구하는지 (점화)식으로 세울 수 있어야 한다.'

 

조금 쉽게 풀어쓰자면 코드는 이렇게 말한다.

'윗 칸에 사자를 두려면 그 전 칸에 사자가 어떻게 위치되어있어야 하지? 존재하지 않아도 되겠다'

그에 반해 나는

'윗 칸에 사자를 두면 그다음에는 텅 비어있거나 아랫 칸에 사자가 위치해있어야겠다.'

 

그리고 그걸 다 떠나서 이번 문제의 포인트를 하나 더 잡자면 2차원 배열(행 혹은 열이 3칸으로 각각 아랫 칸 위치 or  윗 칸 위치 or 텅 빔으로 나타내는 거)을 이용하는 것이다.