[BOJ11727] 2×n 타일링 2

유형: 다이나믹 프로그래밍 (DP)

문제 링크

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

풀이

0. 문제 해석

2×n 크기의 직사각형을 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 문제다. 단, 방법의 수를 10,007로 나눈 나머지를 출력해야 한다.

1. 접근 방법

이 문제는 특정 크기 n의 답을 구하기 위해 그보다 작은 크기의 문제(n-1, n-2)의 답을 활용하는 구조를 가지고 있다. 이는 다이나믹 프로그래밍(DP)을 적용하기에 이상적인 조건이다. n이 1,000까지 주어지므로 모든 경우의 수를 직접 계산하는 것은 불가능하며, DP 테이블을 만들어 점화식을 통해 효율적으로 답을 찾아야 한다.

2. 아이디어

dp[i]를 "2×i 크기의 직사각형을 타일로 채우는 방법의 수"라고 정의하자. dp[n]을 구하기 위해 n번째 열이 어떤 타일로 채워지는지를 기준으로 경우를 나눌 수 있다.

1. 마지막에 2×1 타일이 오는 경우

   n번째 열이 세로로 긴 2×1 타일 하나로 채워진다면, 남은 부분은 2×(n-1) 크기의 직사각형이다. 이 부분을 채우는 방법의 수는 dp[n-1]과 같다.

2. 마지막에 1×2 타일 두 개가 오는 경우

   n-1번째 열과 n번째 열에 걸쳐 가로로 긴 1×2 타일 두 개가 놓인다면, 남은 부분은 2×(n-2) 크기의 직사각형이다. 이 부분을 채우는 방법의 수는 dp[n-2]와 같다.

3. 마지막에 2×2 타일이 오는 경우

   n-1번째 열과 n번째 열에 걸쳐 2×2 타일 한 개가 놓인다면, 남은 부분은 2×(n-2) 크기의 직사각형이다. 이 부분을 채우는 방법의 수 역시 dp[n-2]와 같다.

위 세 가지 경우는 서로 겹치지 않으므로, 전체 경우의 수는 이들을 모두 더한 것과 같다. 따라서 다음과 같은 점화식을 세울 수 있다.

dp[n] = dp[n-1] + 2 * dp[n-2]

점화식을 계산하기 위한 초기값(Base Case)은 다음과 같다.

• dp[1] = 1 (2×1 타일 한 개로 채우는 방법)
• dp[2] = 3 (2×1 타일 두 개, 1×2 타일 두 개, 2×2 타일 한 개로 채우는 방법)

3. 동작 방식

소스코드는 위에서 도출한 점화식을 그대로 구현한다.

1. dp 배열을 N+1 크기로 선언한다.
2. N이 1, 2, 3, 4일 경우는 하드코딩된 값을 바로 출력하는데, 이는 점화식을 이용해 계산해도 동일한 결과가 나온다. DP로 풀 때는 dp[1]과 dp[2]만 초기화해주면 충분하다.
3. dp[1] = 1, dp[2] = 3으로 초기값을 설정한다.
4. 반복이 끝나면 dp[N]에 저장된 최종 결과값을 출력한다.

4. 코드

package BOJ11727;

import java.util.Scanner;

/*
 * f(1) = 1
 * f(2) = 3
 * f(3) = 5
 * f(4) = 11
 * f(5) = 21
 * */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner([System.in](http://System.in));
		int N = sc.nextInt();
		int[] dp = new int[N + 1];
		if (N == 1) {
			System.out.println(1);
			return;
		}
		if (N == 2) {
			System.out.println(3);
			return;
		}
		if (N == 3) {
			System.out.println(5);
			return;
		}
		if (N == 4) {
			System.out.println(11);
			return;
		}

		dp[1] = 1;
		dp[2] = 3;
		dp[3] = 5;
		dp[4] = 11;

		for (int i = 5; i <= N; i++) {
			dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
			//dp[i] = ((dp[i - 1] * 2) + (int) Math.pow(-1, i)) % 10007;
		}
		System.out.println(dp[N]);
	}
}