[백준 C++] 11727번: 2 x n 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

2 x  n 타일링 두번째 문제이다. 

 

첫번째 문제는 내 힘으로 풀지 못했기 때문에 최대한 풀어보고 다른사람이 짠 코드를 보려고 한다. 

 

추가된 규칙은 2 x 2의 타일도 쓸 수 있다는 것

 

처음 생각든 풀이 방법은 2x1 타일을 가로로 두개 둔것과 세로로 두개 둔것을 2 x 2 로 대체할 수 있으므로 그 수만 곱해 주어야 겠다고 생각했다.

 

아니라면 전에 했던 방식대로 n - 1 번째에 오른쪽에 2x1 타일을 놓는것과 n - 2번째에 오른쪽에 2 x2를 놓을 수 있고 기존에 있던 2 x 1을 가로로 두개 둔것을 대체 하는것? 정도 생각해보았다.

 

순열의 경우의 수 팩토리얼

 

n = 1 -> 1

 

n = 2 ->  3

 

n= 3 -> 5

 

n = 4 -> 5 + 6 = 11

 

n = 5 -> 8 + 13 = 21

 

아까 풀이 했을 때 dp[i] = dp[i-1] + dp[i-2] 라는 점화식이 세워졌는데 이는 전꺼에 오른쪽 즉, n-1일때 오른쪽에 2x1타일을 놓고 n-2일때 가장 오른쪽에 2x1타일을 두개 가로로 놓는 경우의 수를 더해준거였지만 이번에 2x2 타일이 새로 생겼으므로 2x1타일을 가로로 두개 놓을때 2x2를 놓는거랑 같으므로 이 경우의 수에 x2만 해주어 최종식은

 

dp[i] = dp[i-1] + 2 * dp[i-2] 라는 식이 나왔다.

 

#include <iostream>
using namespace std;
 
int dp[1001] = { 0 };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;
	
	dp[1] = 1;
	dp[2] = 3;
	dp[3] = 5;
 
 
	for (int i = 4;i <= n;i++) {
		dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
	}
 
	cout << dp[n];
 
 
	return 0;
}

 

솔직히 원리가 크게 와닿지는 않지만 하나하나 대입해보며 생각했을때 결과가 나와 신기하고 뿌듯했다.