[백준] 11726번 : 2×n 타일링

🔗 문제 링크

https://www.acmicpc.net/problem/11726

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 2×(1 ~ n)까지 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

1) n을 입력 받아 저장한다.

2) dp 배열을 선언하고, dp[1]을 1로, dp[2]를 2로 초기화한다.

• dp[i] : 2×i 크기의 직사각형을 1×2, 2×1 크기 타일로 채우는 방법의 수
• dp[1]은 1×2 크기 타일 하나로만 채울 수 있으므로 경우의 수 1
• dp[2]는 2×1 크기 타일 두 개 또는 1×2 크기 타일 두 개로 채울 수 있으므로 경우의 수 2
  

3) dp[3 ~ n]까지 경우의 수를 갱신한다.

• i = 3일 때의 경우를 살펴보면
  • 왼쪽 두 개는 i = 2일 때의 경우에 1×2 크기 타일을 붙인 것
  • 오른쪽 한 개는 i = 1일 때의 경우에 2×1 크기 타일 두 개를 붙인 것

• i = 4일 때의 경우를 살펴보면
  • 위쪽 세 개는 i = 3일 때의 경우에 1×2 크기 타일을 붙인 것
  • 아래쪽 세 개는 i = 2일 때의 경우에 2×1 크기 타일 두 개를 붙인 것

• 위 경우를 일반화하여 점화식으로 나타내면
  • dp[i] = dp[i - 1] + dp[i - 2]
    

4) 최종적으로 2×n 크기의 직사각형을 채우는 경우의 수를 알고 싶은 것이므로 dp[n]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int dp[1001];

void solution()
{
	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] ;
}

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

	cin >> n;
	solution();
}