[C++] 백준 20544 공룡게임

문제 링크

---

www.acmicpc.net/problem/20544

20544번: 공룡게임

 

접근 방법

 

---

 해당문제는 4차원 DP를 사용하여 해결 할 수 있었습니다. 1차원 좌표계에서 4차원 DP를 생각해내는 것이 쉬운 일은 아니었던 문제였습니다.

 

DP의 1~4차원을 설명하자면

1. 현재 위치

2. 현재 높이(0,1,2) 

3. 과거 높이(0,1,2)

4. 높이가 2인 장애물 포함 여부(0,1)

 

 일단 문제를 처음 접근할 때 현재위치와 현재높이를 포함한 DP를 설계해야겠다고 생각했습니다. 이 후 과거의 높이가 다음의 높이 값에 영향을 줄 수 있는 변수라는 것을 알았습니다. 

예를 들어 현재의 값만 생각하였을 때 현재 상태가 1이라면 다음 상태는 0, 1, 2중 어떤 값이 와도 상관이 없습니다. 하지만 과거의 값이 1이었다면 다음 값은 0으로만 갈 수 있게 됩니다.

 

 또한 [현재위치][현재높이][과거높이]가 중복되는 값이 나오더라도 장애물 2를 포함해서 오지 않았다면 다른 경우의 수가 된다는 것을 떠올릴 수 있었습니다. 즉 DP에 장애물 2를 포함했는지의 여부를 나타내는 차원을 추가하였습니다.

 

소스 코드

---

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;
long long dp[1001][3][3][2];
long long mod = 1000000007;
int N;

long long solve(int now, int state, bool flag, int laststate) {

	long long &ref = dp[now][state][laststate][flag];

	if (now == N - 1) {
		if (flag)
			return ref = 1;
		else
			return ref;
	}	
	if (ref != 0)
		return ref;
	
	if (state == 0) {
		ref += solve(now + 1, 0, flag, state) % mod;
		ref += solve(now + 1, 1, flag, state) % mod;
		ref += solve(now + 1, 2, true, state) % mod;
	}
	else if (state == 1) {
		if (laststate == 0) {
			ref += solve(now + 1, 0, flag, state) % mod;
			ref += solve(now + 1, 1, flag, state) % mod;
			ref += solve(now + 1, 2, true, state) % mod;
		}
		else {
			ref += solve(now + 1, 0, flag, state) % mod;
		}
	}
	else if(state == 2){
		if (laststate == 0) {
			ref += solve(now + 1, 0, flag, state) % mod;
			ref += solve(now + 1, 1, flag, state) % mod;
		}
		else {
			ref += solve(now + 1, 0, flag, state) % mod;
		}
	}
	return ref = ref % mod;
}

int main() {

	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> N;

	cout << solve(0, 0, false, 0) << "\n";

}