[Java] 백준 11727번 : 2xn 타일링 2

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

11727번: 2×n 타일링 2

[문제]

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

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

[입력]

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

[출력]

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

 

[예제 입력]

 

[풀이 과정]

- n =1일때 나올 수 있는 경우의 수 1가지

- n =2 일때 나올 수 있는 경우의 수 3가지

- n =3 일때 나올 수 있는 경우의 수 5가지

- n =4 일때 나올 수 있는 경우의 수 11가지 ......

 

즉 : n일때 경우의 수는  n = n-1 + (n-2)*2 임을 알 수 있다. 이 점화식을 가지고 다이나믹 프로그래밍 기법을 이용하여 풀면 된다. 

 

[코드]

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

// 2xn 타일링 2 다이나믹 프로그래밍
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[1001];

        dp[1]=1;
        dp[2]=3;

        for (int i = 3 ; i <1001;i++){
            dp[i]= (dp[i-1]+(2*dp[i-2]))%10007; //점화식
        }

        System.out.print(dp[n]);
    }
}

 

[결과]