문제
2×n 크기의 직사각형을 1×2, 2×1, 2×2 크기의 타일로 채우는 방법의 수를 구한다. 결과는 10007로 나눈 나머지를 출력한다.
입력
- 첫째 줄: 정수 n (1 ≤ n ≤ 1,000)
출력
2×n 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 3 |
9 | 181 |
풀이
11726 문제에서 2×2 정사각형 타일이 추가된 변형이다. dp[n] = dp[n-1] + 2 * dp[n-2]가 점화식이 된다. i-2 위치에서 확장할 때 가로 1×2 타일 2개와 2×2 정사각형 타일 2가지 방법이 모두 가능하기 때문이다.
dp[0] = 1(2×1일 때),dp[1] = 3(2×2일 때:||,==,ㅁ3가지)으로 초기화한다.recur(n)을 재귀 호출하며 메모이제이션으로 중복 계산을 방지한다.dp[n] = dp[n-1] + 2 * dp[n-2]점화식을 적용한다.- 각 반환 시
% 10007을 적용하여 나머지를 유지한다.
핵심 아이디어: 11726과 달리 2×2 타일이 추가되어 i-2에서 확장하는 경우의 수가 2배가 된다. i-1에서 세로 타일 1개를 붙이는 경우는 변하지 않으므로, 결과적으로 dp[n-2]에 곱해지는 계수만 1에서 2로 변경된다.
코드
package com.ssafy.an.day099;
import java.util.Scanner;
public class Day87BOJ11727타일2DP { // 11727 2xn 타일링2
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] = 3; // 2x2칸일 때 || == ㅁ 3가지 경우
System.out.println(recur(N - 1));
sc.close();
}
private static int recur(int n) {
if (dp[n] == null)
dp[n] = recur(n - 1) + 2 * recur(n - 2);
return dp[n] %= 10007;
}
}
// 1(|)과 2(==), 2(ㅁ)를 더하여 N(횡 길이)을 만드는 경우의 수
// 타일1 문제에서
// i-1에 |를 더하는 경우의 수,
// i-2에 ==를 더하는 경우의 수(||은 중복됨.)의 합으로 풀었다.
// 타일2에서는 i-1에 |를 더하는 경우는 동일하지만,
// i-2에 == 또는 ㅁ를 더하는 경우로 2배가 된다.복잡도
- 시간: O(N) — 각 부분 문제를 1회만 계산
- 공간: O(N) — dp 배열 및 재귀 스택