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

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

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

 

---

11727번: 2×n 타일링 2

[ 문제 ]

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 1 ]

#include<iostream>
using namespace std;

int dp[1001];

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

	dp[1] = 1;
	dp[2] = 3;

	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 2 * (dp[i - 2]);
		dp[i] = dp[i] % 10007;
	}

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

[ 코드 2 ]

#include<iostream>
using namespace std;

int dp[1001];

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

	dp[n] = DP(n - 1) + 2 * (DP(n - 2));
	dp[n] %= 10007;
	// 이렇게 해주면 dp[n]에 10007로 나눈 나머지가 들어감
	//cout << dp[n]<<'\n'; // 대충 큰 값을 넣어서 오버플로우 알아보기 (-1값이 나오기 시작)

	return dp[n]%10007;
	// dp[n]%10007만 적어주면, dp[n]에는 나머지가 아닌 원래 값이 들어감
	// 따라서 n이 커지면서 오버플로우가 발생하면 DP(N)이 으수를 반환하기 시작한다.
	// 이 부분에서 dp[n]의 값 또한 변경시켜줄려면 return dp[n]%=10007로 작성해야함
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

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