[연속 dp] 1309 동물원

동물원 (1309)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1309 동물원
const int MAX = 100000;
const int MOD = 9901;
int n;
// cache[i][j] : i 가 마지막 행일 때.
// 				j 가 0이면 해당 열에 아무 사자도 없음 / 1이면 1번째 칸에 사자 / 2면 2번째 칸에 사자
//				가 있을 때의 경우의 수 를 저장한다.
// 가 있을 때의
int cache[MAX + 1][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	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][0] + cache[i - 1][1] + cache[i - 1][2];
		cache[i][1] = cache[i - 1][0] + cache[i - 1][2];
		cache[i][2] = cache[i - 1][0] + cache[i - 1][1];
		
		for(int j = 0; j < 3; j++) cache[i][j] %= MOD;
	}	
	
	cout << (cache[n][0] + cache[n][1] + cache[n][2] ) % MOD << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

0. N <= 100,000 이므로 브루트 포스로는 시간 내에 풀 수 없다.

1. cache 를 어떻게 선언하느냐가 문제의 핵심이자 끝이다.

- 사자가 '연속하면 안된다' 라는 조건을 반영할 수 있게끔 cache (메모이제이션 배열) 을 정의해야만 한다.

항상 '끝에 무엇이 오는지' 를 생각해야 한다.

2. cache[i][j] ( 0 <= j <= 2 ) : 1 ~ i 행까지 있을 때 즉, i 행이 마지막 행일 때,

i 행에 사자가 없을 때, (j = 0)

사자가 1번째 칸에 있을 때, (j = 1)

사자가 2번째 칸에 있을 때, (j = 2)

각각의 경우의 수를 저장한다.

3. 칸마다 연속하면 안되므로,

cache[i][0] = cache[i - 1][0] + cache[i - 1][1] + cache[i - 1][2];
cache[i][1] = cache[i - 1][0] + cache[i - 1][2];
cache[i][2] = cache[i - 1][0] + cache[i - 1][1];

가 된다.

j = 0 일 때를 생각해보면, i 번째 행에 아무 사자도 없을 것이므로, 이전 i - 1번째 행에는 사자가 없든지(j=0) 사자가 1번째 칸에 있든지(j=1) 2번째 칸에 있든지(j=2) 상관없다.

j = 1 일때는, i 번째 행의 1번째 칸에 사자가 있으므로, 이전 i - 1 번째 행에는 사자가 없든지(j=0) 2번째 칸에 사자가 있든지(j=2) 해야 한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점