[Java] 백준(실버-3) 11727번 - 2×n 타일링 2

문제 풀이

---

이 문제는 동적 계획법(DP)를 이용해 풀 수 있는 문제이다.

아이디어 도출

이번 문제는 이전에 풀었던 2xn 타일링 문제와 흠사한 방법으로 풀 수 있다.

2xn 타일링 문제가 피보나치 수열의 형태를 띄고있었다면 이번에는 그 형태가 다르다.

N=1
1x2 => |
총 1가지의 방법

N=2
2x2 => ㅁ
1x2 => ||
2x1 => =
총 3가지의 방법

N=3
2x2, 1x2 => ㅁ|, |ㅁ
1x2, 2x1 => |||, =|, |=
총 5가지의 방법

위 내용을 잘 살펴보면, N이 3일 때는 N=2일 때 타일에 2x1 타일이 세로로 하나 붙은 형태를 가지고 있고, N=1일 때 타일에 2x1 타일이 가로로 2개 붙어있거나, 2x2 타일이 붙은 형태를 지니고 있음을 알 수 있다.

이전 문제에서는 N-2의 타일에 붙이는 타일은 2x1 타일을 가로로 2개 붙인 경우만 가능했었으나, 2x2 타일이 추가되면서 경우의 수가 늘어났다고 볼 수 있다.

따라서, 점화식은 다음과 같이 표현할 수 있다.

dp[n]=dp[n−1]+2×dp[n−2]

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;

class Main {    

    // DP 테이블 선언
    static int[] D;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());

        D = new int[N+1];
        for(int i=0; i<=N; i++) {
            D[i] = -1;
        }

        // 2X0은 0가지, 2X1은 1가지, 2X2은 3가지 경우의 수가 있다.
        D[0] = 0;
        D[1] = 1;
        
        // N이 1일 경우가 있기 때문에 예외처리를 해준다.
        if(N > 1) {
            D[2] = 3;
        }
        
        // 재귀함수 호출한다.
        recursion(N);

          // DP 테이블에 저장된 N번째 값을 출력한다.
        bw.write(D[N]+"\n");

        bw.close();
        br.close();
    }

    /**
     * N=1일 때는 1가지, N=2일 때는 3가지, N=3일 때는 5가지의 방법이 있다.
     * 고로, 점화식은 (N-1) + 2 * (N-2)가 된다.
     */
    static int recursion(int N) {
        if(D[N] != -1) {
            return D[N];    
        }
        return D[N] = (recursion(N-1) + (2 * recursion(N-2))) % 10007;
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.