11726.2xn타일링

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

## 입력

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

## 출력

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

풀이

알고리즘 흐름

문제의 경우의 수를 그려보자.

n=4 까지 확인해보면 일정한 패턴이 반복된다.

위의 그림처럼 노란블럭은 n-1 의 타일에 세로 타일이 1개 추가되고,
빨간블럭은 n-2의 타일에 가로타일이 2개씩 추가된다.

이를 dp로 나타내면,

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

의 점화식을 가지게 된다.

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class _2xn타일링 {  

    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[1002];  

        //bottom up 방식 적용  
        dp[1] = 1;  
        dp[2] = 2;  

        for(int i=3; i<=n; i++){  
            // mod 연산을 한 결과값을 출력할때는 반드시 연산할때마다 mod 연산을 해야한다.  
            // 마지막에만 mod시에 Overflow가 발생할수도 있기 때문.  
            dp[i] = (dp[i-2] + dp[i-1]) % 10007;  
        }  

        System.out.println(dp[n]);  
        br.close();  
    }  
}

DP문제를 처음 접하다보니 나에게는 어려운 문제였다. 문제를 쪼개서 생각해야하는데 막상 마주치면 머리가 하얘진다. 더 연습하자.