[백준] 11727: 2×n 타일링 2 (DP) - JAVA

알고리즘 분류 - dp

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

 

 

 

# 문제

 

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

# 예제

입력 :  첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

12

 

출력 :  첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

2731

 

# 필요개념

어떻게 점화식을 세울지 고민하다가 한 개씩 그려보았다.

 

모양을 하나하나 그려볼까 하다가 귀찮아서 위 사진처럼 그렸는데, 덕분에 점화식을 세우기 쉬워졌다.

n = 3인 경우, n = 1인 타일 뒤에 두 칸을 더 이용할 수 있고 n = 2인 타일 뒤에는 2x1 타일을 붙일 수 있다. 두 칸을 더 이용할 수 있다는 건 1x2인 타일 두개를 붙인 모양 또는 2x2 타일을 붙일 수 있다는 의미가 된다. 

 

n = 4일 때도 같은 방식으로 풀 수 있고 여기서 점화식을 세울 수 있다.

dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;

 

# Code

dp[1]과 dp[2]의 값을 미리 넣어놓다보니, n = 1이 들어오면 인덱스에러가 발생할 수 있어 예외처리를 해두었다.

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[1] = 1;
        if (N > 1) {
            dp[2] = 3;
            for (int i = 3 ; i <= N ; i++) {
                dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;
            }
        }
        System.out.println(dp[N]);
    }
}

 

# 결과