11726(dp)

첫인상

조합을 이용하는 수학문제라고 생각하고 접근했다

문제상황

조합을 이용할게 아니라 dp를 이용하는 문제였고 조합을 이용하게 된다면 시간 초과가 날 확률이 높아 보인다. 코드를 짜면 50줄도 안나오는 쉬운 문제이지만 dp임을 깨달아야 하고 점화식이 피보나치와 같은 모양이 된다는 것을 빨리 깨달아야 할 것 같다.

풀이

피보나치류 dp이다. 마지막에 1x2 타일이 오는 경우 앞에 오는 n-1의 방법의 수와 같고 2x2 타일이 오는 경우 n-2의 방법의 수와 같아서 결국 점화식은 dp[n] = dp[n-1] + n[n-2]가 된다.

코드

#include<iostream>
using namespace std;

int dp[1005];

int main() {
	int n;
	
	cin >> n;

	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	}

	cout << dp[n];
}