[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 2 x n 타일링 (11726)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 2 x n 타일링 (11726)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 2 x n 타일링 (11726)

 

---

 

11726번: 2×n 타일링

[ 문제 ]

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

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

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 1 ]

#include<iostream>
using namespace std;

int dp[1001];
int func(int n) {
	if (n==1)
	{
		return 1;
	}
	if (n==2)
	{
		return 2;
	}
	if (dp[n]>0)
	{
		return dp[n];
	}

	dp[n] = func(n - 1) + func(n - 2);

	return dp[n] % 10007;
	// 피보나치 형식이기 때문에, 매 계산마다 %10007을 해주지 않으면 값이 너무 커질경우 에러가 남

}

int main() {
	int n; // 2 x n 직사각형
	cin >> n;

	cout << func(n);
	return 0;
}

[ 코드 2 ]

#include <iostream>
using namespace std;

int dp[1001];

int main() {
	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];
		dp[i] = dp[i] % 10007;
	}

	cout << dp[n];
	return 0;
}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)