📚 14852 - 타일 채우기 3

타일 채우기 3

 

문제 이해

N-1일 때

 

N-2일 때

 

예외 케이스 (남는 크기가 4일 때)

이와 같이 기존꺼에 2개씩 추가가 된다. (앞에꺼 나오는 수 x 2를 해줘야 한다.)

 

✔️ 점화식

dp[n] = dp[n-1] x 2 + dp[n-2] x 3 + (dp[n-3] x 2 + dp[n-4] x 2 + ~ + dp[0] x 2)

 

arr[i][0]	1	2	7	22	71	228
arr[i][1]	x	x	0	1	3	10

 

 

소스

package Baekjoon.dp;  
  
import java.io.*;  
  
public class BJ14852 {  
  
    static long[] dp;  
    static int N;  
    static long maxNum = 1000000007;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
  
        dp = new long[N + 1];  
  
        dp[0] = 1;  
        dp[1] = 2;  
  
        if (N >= 2) {  
            dp[2] = 7;  
            long tmp = 0; // i-2, i-1번째 제외 나머지로 만들 수 있는 타일  
            for (int i = 3; i <= N; i++) {  
                dp[i] = (dp[i - 2] * 3 % maxNum + (dp[i - 1] * 2) % maxNum + 2 * (tmp += dp[i - 3])) % maxNum;  
            }  
            System.out.println(dp[N]);  
        } else {  
            System.out.println(dp[1]);  
        }  
  
  
    }  
}

 

💡 참고
나동빈 수업 영상 참고하면 쉽게 이해가 될것이다.
수업 영상 : https://www.youtube.com/watch?v=kYoKLm8BZtI