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

[BOJ] C/C++ 11726 "2xn 타일링" 문제풀이

난이도 : SILVER3

---

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

---

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

---

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

소스코드

#include <iostream>
using namespace std;

int main() {
	int rec[1001];
	int N;
	cin >> N;

	//init
	rec[1] = 1;
	rec[2] = 2;

	for (int i = 3;i <= N;i++) {
		rec[i] = (rec[i - 1] + rec[i - 2]) % 10007;
	}

	cout << rec[N] << endl;
	return 0;
}

---

풀이

2xN 의 직사각형이 있을 때, 오른쪽으로 한 칸 확장하는 방법은 2가지이다.

(rec[N] 을 2XN 직사강형으로 만들 수 있는 최대 가짓수라 가정한다.)

 

방법 1 > 이전에 만들어 둔 직사각형의 오른쪽에 1X2 블록을 하나 추가한다.

 

방법 2 > 전전에 만들어 둔 직사각형의 오른쪽에 2X1 블록을 2개 추가한다.

 

 

EX> N = 5 인 경우

 

방법 1 > N = 3 , 2X3 직사각형을 채우는 가짓수 (3가지) rec[N-2]

 

방법 2 > N = 4 , 2X4 직사각형을 채우는 가짓수 (5가지) rec[N-1]

 

따라서, rec[5] N = 5 인 경우의 가짓수는 rec[3] N = 3 (3가지) + rec[4] N = 4 (5가지) 8가지

 

이를 , 점화식으로 작성해 보면

rec[N] = rec[N-2] + rec[N-1]

 

이 점화식을 코드로 표현하면 된다.

---

www.acmicpc.net/problem/11726

11726번: 2×n 타일링