[C++/groom] Lv.3 : 거리두기 (DP)

 

https://level.goorm.io/exam/160279/%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0/quiz/1

구름LEVEL

---

구름 레벨 3. 

DP와 경우의 수 전처리 계산값(?)을 적절히 사용해야 한다

구름은 이런 유형이 많은가.. 익숙하지 않아서 더 오래걸린다 ㅠㅠ

 

각 상태 별 경우의 수를 찾아서 dp에 적절히 더해줘야 한다!

dp[i][j] -> i번째 줄의 상태가 j(0~5)일 때의 누적 경우의 수로 해결했다.

 

 

나의 풀이

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n=0;
	int mod = 100000007;
	int dp[100001][5] = {0,}; // i번째 줄의 상태가 j일때, 경우의 수
	int answer = 0;
	
	// 0 {0,0,0}; // 5경우의 다음에 올 수 있음
	// 1 {1,0,0}; // 3
	// 2 {0,1,0}; // 4
	// 3 {0,0,1}; // 3
	// 4 {1,0,1}; // 2

	cin >> n;
	for(int j=0; j<5; ++j){
    dp[1][j] = 1; // 1번째 줄 상태 초기화
	}
	for(int i=2; i<=n; ++i){
		dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % mod;
		dp[i][1] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % mod;
		dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % mod;
		dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % mod;
		dp[i][4] = (dp[i-1][0] + dp[i-1][2]) % mod;
	}
	for(int j=0; j<5; ++j){
    answer += dp[n][j];
		answer %= mod;
	}
	cout << answer;
	return 0;
}