득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 2. 4. 19:42
 

11726번: 2×n 타일링

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

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;
	DP[2] = 2;
	for (int i = 3; i <= N; ++i)
	{
		DP[i] = DP[i - 1] + DP[i - 2] % 10007;
	}

	cout << DP[N] % 10007;
}

 

DP 문제입니다.

 

타일의 윗줄만 보았을 때 1칸 또는 2칸의 덧셈을 나열하는 경우의 수를 구하도록 점화식을 세웠습니다.

문제의 예시 그림에 경우는 1 + 1 + 2 + 1라고 볼 수 있습니다.

 

그리고 테이블에 값을 저장할 때도 mod를 해주어야 해당 값이 자료형의 크기를 넘어가지 않습니다.