[BOJ/백준 11726][C++] 2xn 타일링

문제

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

 

문제 내용

2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 가지 수를 구하는 문제이다.

 

문제 풀이

문제를 읽어보면 느껴지겠지만, dynamic programming  문제이다.
dp 문제의 핵심은 규칙 찾기이다.

 

이 문제의 규칙을 찾아보자.

dp[1]=1 이다.  // I

dp[2]=2 이다.  // II, =

dp[3]=3 이다.  // III,I=,=I

dp[4]부터 확인해 보자.
dp[3]왼쪽에 I추가하는 경우  =>   IIII,II=,I=I
dp[2]왼쪽에 =추가하는 경우  =>   =II,==
따라서 dp[4]=5이다.

dp[5]도 확인해 보자.
dp[4]왼쪽에 I추가하는 경우  =>   IIIII,III=,II=I,I=II,I==
dp[3]왼쪽에 =추가하는 경우  =>   =IIII,=II=,=I=I
따라서 dp[5]=9이다.

위의 두 경우에서 규칙을 추론해보자.
dp[n] = dp[n-1] + dp[n-2] 가 나온다.
오른쪽을 고정시켜두고 왼쪽에 새로운 것을 추가하는 방식으로 문제를 해결했다.
왼쪽을 고정시키고 오른쪽에 새로운 것을 추가해도 된다.
(뭐든 하나만 하면 된다.)

 

코드

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

int dp[1005];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	//입력
	int n; cin >> n;
	dp[1] = 1;  // I
	dp[2] = 2;	// II, =
	dp[3] = 3;  // III,I=,=I

	//dp[4]의 경우 5이다. (n-1)+(n-2)
	//dp[3]왼쪽에 I추가   IIII,II=,I=I
	//dp[2]왼쪽에 =추가   =II,==

	//dp[5]의 경우 8이다.
	//dp[4]왼쪽에 I추가   IIIII,III=,II=I,I=II,I==
	//dp[3]왼쪽에 =추가   =IIII,=II=,=I=I

	//문제 해결
	for (int i = 4; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2])%10007;
	}

	//결과 출력
	cout << dp[n] << '\n';

}

 

문제 코드 설명

1) 문제 해결

반복문을 통해 dp[n]의 값을 구하면 된다.
이때 출력 조건이 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 이므로 dp[n-1]+dp[n-2]를 10007로 나눈 나머지를 dp[n]에 넣으면 된다.