[백준/DP] 11726번 2xn 타일링 (JAVA)

문제

똑같은 문제가 프로그래머스에도 있었다. 예전에 풀었던 기억이 있는데 그 때는 처음에 접근할 때 DP를 사용하지 않는 방법을 사용했던 것 같다. 링크에 들어가보니 맞다^^;;

풀이

이번엔 바로 DP로 접근해서, 부분값을 새로운 값으로 어떻게 연결시킬지를 먼저 생각해보았다. 그림을 직접 연습장에 그려서 보니 아래와 같은 규칙을 발견할 수 있었다.

2xi 타일을 채울 때,

• 맨 끝에 2x1 막대 한 개를 추가하면 나머지 2x(i-1)을 채우는 경우의 수를 세야 한다. 이것은 dp[i-1]의 값과 같다.
• 맨 끝에 1x2 막대 두 개를 추가하면 나머지 2x(i-2)를 채우는 경우의 수를 세야 한다. 이것은 dp[i-2]의 값과 같다.

부분합을 활용하기 위해서는 맨 왼쪽이나 맨 오른쪽 끝에 막대를 추가하는 방식으로 가야 한다. 중간에 끼워 넣으면 중복이 생기고 부분합을 활용할 수 없기 때문이다. 기존의 블록 조합에 막대를 하나 갖다 붙이는 것이 중복되지 않은 새로운 블록 조합을 만드는 방법이다.

따라서 dp[i] = dp[i-1] + dp[i-2]라는 점화식을 세울 수 있다.
이를 바탕으로 작성한 코드는 아래와 같다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;
    private static final int MOD = 10007;

    private static int n;
    private static int[] dp = new int[MAXIMUM + 1];

    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());
        dp();
        bw.append(String.valueOf(dp[n]));

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

    private static void dp() {
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }
}

저번에는 각 n마다 하나하나 경우의 수를 센 다음 숫자들에서 피보나치를 우연히 발견한 것이었다. 하지만 이번엔 그림에서 명확히 보이는 규칙을 찾아내서 점화식을 세운 것이고, 그것이 우연찮게 피보나치가 된 것이다. 이번에 푼 방식이 훨씬 DP답고 효율적이었던 것 같다. 쉬운 문제지만 일단 만족만족.