Problem 11726

2xn타일링

문제

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

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

입력

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

출력

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

문제 링크

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

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

solve

• 먼저 메모이제이션 할 배열 d[]를 선언한다.

• 점화식 d[n] = 2xn 크기의 직사각형을 채우는 방법의 수

  • 2xn 크기의 직사각형에 타일을 추가로 붙이는 경우
  • 1. 2x1 타일을 하나 붙인다.
  • 2. 1x2 타일을 두 개 붙인다.

• 즉, 2xn 크기의 직사각형을 채우는 방법의 수는

• 2x(n-1)의 직사각형에 2x1타일을 하나 붙이는 경우의 수 + 2x(n-2)의 직사각형에 1x2타일을 두 개 붙이는 경우의 수

• d[n] = d[n - 1] + d[n - 2]

• 피보나치 수열과 같은 형태로 점화식이 만들어진다.

코드 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<iostream>

using namespace std;
int d[1001] = { 0 }; // d[n] = 2xn 크기의 직사각형을 채우는 방법의 수
int tiling(int n) // top-down 방식
{
	if (n <= 2) // n이 d[1] = 1, d[2] = 2이므로
		return n;
	if (d[n] > 0) // 이미 구한 경우
		return d[n];
	else
	{
		d[n] = tiling(n - 1) + tiling(n - 2); // d[n] = d[n - 1] + d[n - 2]
		d[n] %= 10007; // 10007로 나눈 나머지 출력
	}
	return d[n];
}
int tiling1(int n) // bottom-up 방식
{
	d[1] = 1;
	d[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		d[i] = d[i - 1] + d[i - 2];
		d[i] %= 10007; // 10007로 나눈 나머지 출력
	}
	return d[n];
}

int main(void)
{
	int n;
	cin >> n;

	cout << tiling(n) << '\n';
}

• ← Previous Post
• Next Post →