백준 c++ 11727 "2×n 타일링 2" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자 사고]

 

동적프로그래밍이다.

 

필자는 dp[i]를 다음과 같이 정의하였다.

 

dp[i] = dp[i-2]*2 + dp[i-1];

 

dp[i-2]의 의미는 현재 플록에서 2cm를 뺀 그동안 쌓아온 블록의 수를 의미한다. *2를 한 이유는 

 

2cm간의 빈 공간을 어떠한 타일로 채울 것인지에 대한 의미이다.

 

1x2 인 형태인 타일을 위 아래로 놓는 경우의 수와 

 

2X2 타일 한개를 넣는 경우의 수 총 2개라고 생각하여 

 

곱셈 연산을 해주었다.

 

여기서 중요한 점은 2x1 타일 즉 위 아래로 기다란 타일의 경우의 수를 뺀 이유는 dp[i-1] 때문이다. 

 

dp[i-1]은 위와 같이 1cm의 빈 곤강을 의미하므로 자동적으로 하나의 경우의 수밖에 존재 하지 않는다.

 

좀더 수식적으로 맞는 표현은 dp[i-1]*1 이라고 할 수 있다.

 

이 풀이 과정만 알면 아래와 같이 코드를 짜면 된다.

 

[소스 코드]

 

#include<iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int N;
vector<int> Dp;

void Input() {
	
	cin >> N;
	Dp.resize(1001);
	Dp[1] = 1;
	Dp[2] = 3;
}

void Solve() {
	for (int i = 3; i < 1001; i++) {
		Dp[i] = Dp[i - 2] * 2 + Dp[i - 1];
		Dp[i] = Dp[i] % 10007;
	}
}

int main(void) {
	Input();
	Solve();
	cout << Dp[N];
}