문제
2×n 크기의 직사각형을 1×2 또는 2×1 크기의 타일로 채우는 방법의 수를 구한다. 결과는 10007로 나눈 나머지를 출력한다.
입력
- 첫째 줄: 정수 n (1 ≤ n ≤ 1,000)
출력
2×n 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 2 |
9 | 55 |
풀이
dp[n]을 2×n 직사각형을 채우는 방법의 수로 정의한다. 마지막 열을 채우는 방법은 세로 1×2 타일 1개(dp[n-1]에서 확장)이거나 가로 2×1 타일 2개(dp[n-2]에서 확장)이므로 점화식은 dp[n] = dp[n-1] + dp[n-2]이다.
dp[0] = 1(2×1일 때 세로 타일 1가지),dp[1] = 2(2×2일 때 2가지)로 초기화한다.recur(n)을 재귀 호출하며 메모이제이션으로 중복 계산을 방지한다.- 각 반환 시
% 10007을 적용하여 나머지를 유지한다.
핵심 아이디어: 2×n 타일링의 경우의 수는 피보나치 수열과 동일한 점화식을 따른다. 가로 타일은 반드시 2개가 쌍으로 와야 하므로 i-2에서만 확장되고, || 패턴(세로 2개)은 i-1에서 확장되는 경우에 포함되어 중복 없이 계산된다.
코드
package com.ssafy.an.day099;
import java.util.Scanner;
public class Day86BOJ11726타일1DP { // 11726 2xn 타일링
static int N;
static Integer[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
dp = new Integer[N];
dp[0] = 1; // 2x1 칸일 때
if (N > 1) dp[1] = 2;
System.out.println(recur(N - 1));
sc.close();
}
private static int recur(int n) {
if (dp[n] == null)
dp[n] = recur(n - 1) + recur(n - 2);
return dp[n] %= 10007;
}
}
// 2x1 |
// 2x2 || ==
// 2x3 |== ==| |||
// 2x4 ==== |==| ||== ==|| ||||
// 2x5 |==|| ||==| ||||| |==== ====|
// --- |||== ==||| ==|==
// 2x6 ====== |==|== ||==== ==||== ||||==
// --- |==||| ||==|| |||||| |====| ====||
// --- |||==| ==|||| ==|==|
// 값 자체는 피보나치 수열과 같은 증가 양상을 보이지만,
// 실제로는 1(|)과 2(==)를 더하여 N(횡 길이)을 만드는 경우의 수복잡도
- 시간: O(N) — 각 부분 문제를 1회만 계산
- 공간: O(N) — dp 배열 및 재귀 스택