[C++][DP][백준] 2×n 타일링 2 :: seoftware

 

---

 

문제 접근

---

2020/04/07 - [IT/코딩테스트] - [C++][백준] 11726번 2×n 타일링 :: seoftware

[C++][백준] 11726번 2×n 타일링 :: seoftware

 

이전 문제랑 매우 유사하다. 둘 다 이전까지 구한 값을 바탕으로 관계식을 세워서 푸는 다이나믹프로그래밍 문제이다.

다만 다른 점은 이 전에는 n-2에서 n이 되는 경우가 한 가지, n-1에서 n이 되는 경우가 1가지 였는데,

이 문제에서는 n-2에서 n이 되는 경우가 2가지라는 점이다.

따라서 dp[n] = dp[n-2] * 2 + dp[n-1] 로 값을 구할 수 있다.

 

 

소스코드

---

 

#include <iostream>
using namespace std;

int dp[1001];

int main(void) {
	int N; cin >> N;
	dp[1] = 1; dp[2] = 3;
	for (int i = 3; i <= N; i++) {
		dp[i] = (2*dp[i - 2] + dp[i - 1]) % 10007;
	}
	cout << dp[N] << endl;
}