득이공간

[백준 C++] 11727 2×n 타일링 2 - 다이나믹프로그래밍 본문

PS/알고리즘 문제풀이

[백준 C++] 11727 2×n 타일링 2 - 다이나믹프로그래밍

쟁득 2024. 2. 15. 17:25
 

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

#include <iostream>
using namespace std;

int DP[1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N;
	cin >> N;

	DP[1] = 1;
	for (int i = 2; i <= N; ++i)
	{
		if ((i - 1) % 2 == 1)
		{
			DP[i] = DP[i - 1] * 2 + 1;
		}
		else
		{
			DP[i] = DP[i - 1] * 2 - 1;
		}
		DP[i] %= 10007;
	}

	cout << DP[N];
}

 

점화식을 도출해서 푸는 다이나믹 프로그래밍 유형의 문제입니다.

 

n이 1~6일 때의 각 경우의 수 1, 3, 5, 11, 21, 43 에 따라 일반화 된 점화식은 다음과 같습니다.

DP[i] = DP[i -1] * 2 + 1 (i-1이 홀수 일때)

DP[i] = DP[i -1] * 2 - 1 (i-1이 짝수 일때)

 

다른 분들의 풀이를 보니 다음과 같은 점화식을 사용해서 푸는 방법도 존재했습니다.

DP[i] = DP[i - 1] + DP[i -2] * 2