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

문제

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

11727번: 2×n 타일링 2

 

문제이해

• 째 줄에 n을 입력합니다.
• 2xn 크기의 직사각형을 채우는 방법을 10007로 나눈 값을 출력합니다.

 

이 문제는 다이나믹 프로그래밍을 사용하는 문제입니다. 사용할 수 있는 블록은 2x1로 된 가로블록, 1x2로 된 세로 블록, 2x2로 된 정사각형 블록으로 총 3개가 있습니다.

 

점화식을 찾기 위해 우선 배열을 통해 설명해 보겠습니다. 2xi 크기의 직사각형을 채우는 방법을 의미합니다.

 

dp [1]은 세로블록 한 개의 경우밖에 없으므로 1입니다.

dp [2]는 세로블록 두개 또는 가로블럭 두개 또는 정사각형 블럭 한 개의 경우가 있으므로 3입니다.

dp [3]은 확인해 보면 5입니다.

 

dp [2]를 통해 dp [4]를 만드는 방법은 오른쪽에 가로블록 두개를 놓거나 세로블럭 두 개를 놓거나 정사각형 블럭 한 개를 놓는 방법이 있습니다.

dp [3]을 통해 dp [4]를 만드는 방법은 오른쪽에 세로블록 한 개를 놓는 방법이 있습니다. 다만 dp [3]의 오른쪽에 세로블록 한 개를 놓는 방법은 dp [2]를 통해 dp [4]를 만드는 방법 중 한 개와 겹치기 때문에 dp [2]에서 dp [4]를 만드는 방법을 총 두 개뿐인 것으로 해야 합니다.

 

이를 통해 얻을 수 있는 점화식은

dp [i + 2] = dp[i + 1] + dp [i] + dp [i]이고 이는 dp [i + 2] = dp[i + 1] + 2 * dp [i]라고 할 수 있습니다.

 

아래의 코드는 해당 점화식을 통해 dp [i]의 값을 알아내 출력하는 정답 코드입니다.

 

문제풀이

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

vector<long long> dp(1001);

void method() {
	dp[1] = 1;
	dp[2] = 3;
	for (int i{ 3 }; i < dp.size(); i++) {
		dp[i] = dp[i - 1] +  2 * dp[i - 2];
		dp[i] %= 10007;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	method();
	int N;
	cin >> N;
	cout << dp[N];
}

 

 

문제후기

점화식이 찾기 쉬워 어렵지 않은 문제였습니다.