[DP/자바] 코드트리 IL. 사각형 채우기 3

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

이 문제는 지난번에 풀었던 "사각형 채우기"와 같은 유형의 문제로써, 점화식을 세울 때 조금 더 생각을 해줘야 하는 문제이다.

 

기본적으로 n번째 자리까지 타일을 까는 경우의 수는 n-1, n-2 번째까지의 타일을 까는 경우의 수 들을 이용하여 도출해낼 수 있다는 아이디어가 DP의 기본 흐름이다.(큰 문제는 작은 문제로 쪼개어 생각한다.)

이렇게 볼 때, 1칸짜리 그리고 2칸짜리를 이용하여 f(n) = 2 * f(n-1) + 3 * f(n-2) 까지는 쉽게 구해질 것이다. 이게 만약 안보인다면 DP를 조금 더 연습해본 뒤 이 문제를 풀길 권한다.

이제부터 필자가 어려워했던 부분인데, 해당 문제는 2칸짜리를 이용하여 벽돌처럼 교차하면서 이어나갈  수 있는 경우까지 고려해야 한다. 근데 이 경우가 n-3, n-4, n-5 등 어디서든 최소한의 길이가 확보된 지점에서부터 모든 항에 적용된다.

 

그 외에는 적절하게 MOD 연산을 넣어줘야 하는 점을 고려해야 한다.

                                 

문제 풀이                      

package 코드트리.DP;

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

public class 사각형_채우기_3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[1001];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 7;

        for (int i = 3; i <= 1000; i++) {
            dp[i] = mod(mod(2 * dp[i - 1]) + mod(3 * dp[i - 2]));
            for (int j = i-3; j >= 0; j--) {
                dp[i] = mod(dp[i] + mod(2 * dp[j]));
            }
        }
        System.out.println(dp[n]);

    }

    private static long mod(long num) {
        return num % 1000000007;
    }
}