[백준/C++]#11727 - 2xn 타일링2

풀이

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int D[1001];
	D[1]=1, D[2]=3;
	for (int i=3; i<=n; i++) {		//n의 크기에 따라 반복
		D[i] = D[i-1] + 2*D[i-2];	//값을 배열에 저장
		D[i] = D[i] % 10007;
	}
	cout << D[n];
	return 0;
}

개념

지난번에 푼 #11726의 2번째 버전이다.

이번에도 Bottom-Up 방식으로 순환호출을 사용하지 않고, 반복문을 사용해 문제를 해결했다.

이 방식이 코드를 해석할 때 좀 더 직관적인 것 같다.

---

풀이 

 

ppt를 사용해 그려보았다

2xn (ver.2)의 타일링 경우의 수는 D[n]이다. 그리고 D[n]은 D[n-1] +2*D[n-2]이다.

지난 문제와 달라진 점은, 2x1 2개 대신 2x2가 올 수 있다는 것이다.

D[n-1]에 1x2를 더해주는 경우는 동일하지만, D[n-2]에 2x1 2개를 더할 수도, 2x2 1개를 더할 수도 있다.

따라서 D[n-2]에 2를 곱해주면 된다.