[백준 / C++] Day90. 2xn 타일링

2024. 09. 01 - 코딩테스트 스터디 Day90

 
 

01. 문제

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

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

 
 

02. 입력

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

03. 출

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

04-1. 예제 입력 1

2

 
 

04-2. 예제 출력 1

2

 

 

05-1. 예제 입력 2

9

 
 

05-2. 예제 출력 2

55

 

 

6. 풀이 및 답 

n에 따른 2×n 크기의 직사각형을 채우는 방법의 수는 아래와 같다
n = 1 → dp[1] = 1
n = 2 → dp[2] = 2
n = 3 → dp[3] = 3
n = 4 → dp[4] = 5
n = 5 → dp[5] = 8
 
위 결과를 통해 아래와 같은 점화식을 구할 수 있다
dp[i] = dp[i - 1] + dp[i - 2]
 

#include <iostream>

using namespace std;

int main() {
	int dp[100001];
	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;
}

위 점화식을 가지고 코드를 작성해보았다.
 
 

정답!

---