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

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

문제 링크

성능 요약

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

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 3일 18:28:08

문제 설명

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

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

 

입력

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

출력

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

풀이

이전 포스트와 연결되는 문제이다.

https://2junbeom.tistory.com/93

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

위의 풀이를 보면 N = N-1인 경우에 세로 짝대기 한 개 더한 경우  + N-2인 경우에 가로짝대기 두 개 더한 경우와 같다.

 

이 문제는 정사각형 타일이 하나 추가됐다.

 

정사각형 타일이 더해질 수 있는 곳은 N-2밖에 없으니 

 

기존의 점화식이었던, N = N-1 + N-2 에서

 

N = N-1 + (N-2) * 2 로만 변경해주면 문제를 해결할 수 있다.

 

전체 코드

public class Main {
    static int N=0;
    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] = 3;
        if(N > 2) {
            for (int j = 3; j <=N;j++){
                dp[j] = (dp[j-1] + (dp[j-2]*2)) % 10007;
            }
        }

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

    }
}