바닥 공사 - '이것이 코딩 테스트다 with 파이썬'

이것이 취업을 위한 코딩 테스트다 with 파이썬

바닥이 세로(2) x 가로(N) 으로 되어 있는 바닥을 덮을 때, (1 x 2), (2 x 1), (2 x 2) 덮개로 채울 수 있는 모든 경우의 수를 출력 하는 문제 입니다. 결과 값이 클 수 있으므로 796,796으로 나눈 나머지를 출력 하는 문제 입니다.

 

이 문제의 점화식은 (i - 1) 인 경우는 (2 x 1) 타일 하나 만 덮을 수 있는 경우가 존재 합니다. (i - 2)의 경우는 (1 x 2) 2개 로 덮는 경우와, (2 x 2) 1개로 덮는 경우 2가지가 존재 합니다. 따라서 점화식은 dp[i] = dp[i-1] + (dp[i-2] x 2) 로 세울 수 있습니다. 

 

public class Page223 {
    //N = 1일때 1개 (2*1)
    //N = 2일때 3개 (2*1, 2*1) (1*2, 1*2) (2*2)
    //N = 3일때 5개 (2*1, 2*1, 2*1) (1*2, 2*1, 2*1) (2*1, 2*1, 1*2) (2*2, 2*1) (2*1, 2*2)
    // dp[i] = dp[i-1] + (2 * dp[i-2])
    public static void main(String[] args) {
        System.out.print(new Page223().solution(3));
    }

    int solution(int N){
        int[] dp = new int[N+1];
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= N; i++) {
            dp[i] = dp[i-1] + (2 * dp[i-2]) % 796796;
        }
        return dp[N];
    }
}