[백준/C++] 11726 2xn 타일링 (S3)

유형	난이도	완료일	링크	특이사항
DP	실버3	23/03/26	https://www.acmicpc.net/problem/11726

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	
	int n;
	
	cin >> n;
	
	int arr[1001] = {};
	arr[1] = 1;
	arr[2] = 2;
	
	
	for(int i= 3; i<=n; i ++)
	{
		arr[i] = (arr[i-1]%10007 + arr[i-2]%10007)%10007;
	}
	
	cout << arr[n];
}

  n = 6인 경우까지 답을 나열해보자. arr[i] = arr[i-1] + arr[i-2] 라는 점화식을 발견할 수 있었다.

이렇게 막 적어서 왜 그런지도 모른채 점화식만 남기지 말고 그 점화식이 왜 성립하는지도 생각해봐야겠다.

 

https://kosaf04pyh.tistory.com/222

 

  그림을 보면 이해가 쉽다. dp[n] = dp[n-1] + dp[n-2]가 성립하는 이유는 dp[n-1]에 세로 막대를 하나 추가하는 경우(막대 하나가 들어갈 순서에 따라서도 다른 경우로 취급하지만 결국 모든 경우가 n-1번째에 이미 고려되어 있는 것이다)와 dp[n-2]에 가로 막대 두 개를 추가하는 경우를 합한 것이 dp[n]이기 때문이다.

막대를 놓는 순서에 따라서도 다른 경우가 된다는 것 때문에 헷갈리지만 오른쪽/왼쪽 등에 관계 없이 기준으로 한 곳을 정하고 나면 그곳에 세로 막대 하나, 혹은 가로 막대 둘이 추가되는 경우로 좁혀진다는 것을 확인할 수 있다.