백준/11726번 :: 2xn 타일링 (Java 구현) - DP 다이나믹 프로그래밍

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력1

2

 

예제 출력1

2

 

 

예제 입력2

9

 

예제 출력2

55

 

코드 구현

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

public class Ex11726 {

    // d[n] = d[n-1] + d[n-2];
    private static int[] d;
    private static void process(int n) {
        for(int i=0; i<=n; i++) {
            if(i <= 2) d[i] = i;
            else {
                d[i] = (d[i-1] + d[i-2]) % 10007;
            }
        }
    }
    
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(br.readLine());
            d = new int[n+1];
            process(n);
            System.out.print(d[n]);
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }
}
​

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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

 

관련 글

2018/05/02 - [Algorithm] - 알고리즘 :: 다이나믹 프로그래밍(DP) - 피보나치(Fibonacci) C/C++ 구현, 메모이제이션

2018/05/02 - [Algorithm/백준 온라인 저지] - 백준/11726번 :: 2xn 타일링 (C/C++ 구현)

2018/05/02 - [Algorithm/백준 온라인 저지] - 백준/11727번 :: 2xn 타일링 2 (C/C++ 구현)

2018/06/19 - [Algorithm/백준 온라인 저지] - 백준/11727번 :: 2xn 타일링 2 (Java 구현) - DP 다이나믹 프로그래밍