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

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

11726번: 2×n 타일링

 

다이나믹 프로그래밍으로 풀 수 있는 문제이다.

 

n 이 주어지고 그에따라 직사각형을 넣을 수 있는 경우의 수를 계산하는 문제이다.

 

우선 규칙을 찾기 위해 1부터 넣어보자

 

1 - > 1

 

2 - > 2

 

3 - > 3

 

4 - > 5

 

5 - > 8

 

그림으로 그려보자면

다음은 n  = 2일때 경우의 수

 

n = 3일떄 경우의 수

 

(1)

(2)

(3)

 

n = 2과 n = 3일때를 비교했을때  (1), (2)는 n = 2 에 경우의 수에  1 x 2 타일을 오른쪽의 붙인 모양과 같고, (3)는 n = 1 경우의 수에 2 x 1  타일을 오른쪽의 붙인 모양이랑 같다. 따라서 점화식을 작성해보면 

 

dp[i] = dp[i-1] + dp[i-2] 입니다.

 

또한, 숫자가 너무 커질 수도 있기 때문에 10007을 나눈 값을 배열에 넣어준다.

 

전체코드는 이렇다.

#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] = 2;
 
	for (int i = 3;i <= n;i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	}
 
	cout << dp[n];
 
 
	return 0;
}

 

규칙을 혼자 생각해보려 했지만 너무 생각이 안나 답을 보고 푼 문제이다. dp의 규칙을 생각하는 능력과 경우를 좀 더 키워야겠다.