[백준 - 14852][GOLD 4][해설 X] - 타일 채우기 3 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/14852

 

문제

---

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

 

입력

---

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

 

출력

---

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

해결 코드

---

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

/*
 *
 *   dp[n][전체] = dp[n-1](2*1와 1*1을 세로로 붙인경우) + dp[n-2](1*2를 2개붙인 경우) + dp[n-1](위에만 튀어나온 경우에 1*1과 1*2를 사용한 경우) +  dp[n-1](아래만 튀어나온 경우에 1*1과 1*2를 사용한 경우)
 *              = dp[n-1][전체] * 2 + dp[n-2][전체] + dp[n-1][위] + dp[n-1][아래]
 *
 *   dp[n][위] = dp[n-1](전체에 위에만 1*1 블록을 붙인경우) + dp[n-1][아래](위에다가 1*2를 븥인 경우)
 *             = dp[n-1][전체] + dp[n-1][아래]
 *
 *   dp[n][아래] = dp[n-1](전체에 아래에만 1*1 블록을 붙인경우) + dp[n-1][위](아래에다가 1*2를 븥인 경우)
 *             = dp[n-1][전체] + dp[n-1][위]
 * */

public class Main {
    static int TOTAL = 0;
    static int UP = 1;
    static int DOWN = 2;
    static int MOD = 1_000_000_007;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        long[][] dp = new long[1_000_000+1][3];

        dp[1][TOTAL] = 2;
        dp[1][UP] = 1;
        dp[1][DOWN] = 1;

        dp[2][TOTAL] = 7;
        dp[2][UP] = 3;
        dp[2][DOWN] = 3;

        for(int i=3;i<=N;i++){
            dp[i][TOTAL] = (dp[i-1][TOTAL] * 2 + dp[i-2][TOTAL] + dp[i-1][UP] + dp[i-1][DOWN]) % MOD;
            dp[i][UP] = (dp[i-1][TOTAL] + dp[i-1][DOWN])%MOD;
            dp[i][DOWN] = (dp[i-1][TOTAL] + dp[i-1][UP])%MOD;
        }

        System.out.println(dp[N][TOTAL]);
    }
}

 

 

실행 결과

---

 

팁

---

• 높이가 1보다 크면 각 높이의 최대/최소값을 구하고 점진적으로 구하는 방법을 생각해보자