백준 11726번 2xn 타일링 (java)

[Silver III] 2×n 타일링 - 11726

문제 링크

성능 요약

메모리: 14372 KB, 시간: 104 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 3일 01:50:06

문제 설명

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

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

입력

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

출력

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

풀이

일단 2x1 부터 차례 차례 모든 경우의 수를 그려보았다.

일단 적어보고 나니까 N = N-1 + N-2 라는 규칙이 보였다.

 

그리고 천천히 이유를 생각해보니

 

N에서 나올 수 있는 경우의 수는 N-1에 세로 두 칸짜리 블럭 하나를 붙이는 것과

 

N-2에 가로 두 칸자리 블럭 두 개를 붙이는 경우의 수밖에 없다는 것을 알 수 있었다.

 

N-2에 세로 두 칸짜리 두 개를 붙이는 경우의 수는 왜 더하지 않느냐 라고 물어볼 수 있다.

 

더하지 않는 이유는 N-1에 이미 N-2에서 세로 두 칸짜리 블럭 한 개를 더해놓은 상태기 때문에

 

N-1에 세로 두 칸 짜리 블럭 한 개를 더하는 것이 N-2에서 세로 두 칸짜리 블럭 두 개를 더한 것을 이미 포함하고 있는 것 과 마찬가지기 때문이다.

 

전체 코드

public class Main {
    static int N=0,dp[];
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        N = Integer.parseInt(br.readLine());

        int dp[] = new int[N+3];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        if(N > 3) {
            for (int j = 4; j <=N;j++){
                dp[j] = (dp[j-1] + dp[j-2]) % 10007;
            }
        }

        bw.write((dp[N]) + "");
        bw.flush();

    }
}