(Baekjoon) dp - (6) 타일 채우기 3

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

14852번: 타일 채우기 3

 

 

 

dp(n) = 2*dp(n-1) + 3*dp(n-2) + 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0))

위의 그림과 같은 과정을 통해 위의 점화식을 도출할수 있다.

 

그리고 코드를 짜서 제출할경우 시간초과를 겪는데 그러한 이유를 살펴보면은

 

 

 

2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 부분에서 계속 구한값을 다시 계산하고 다시계산하는것을 알수있다.

이부분 또한 동적프로그래밍 기법을 적용하여서 한번구한값은 다시 구하지 말자라는 방식을 써야한다.

 

int는 값이 작아서 그런가 실패가 떠서 long으로 바꿔주었다.

 

 

컴퓨터에게 두번일시키지말아라!!! 그것이 동적프로그래밍의 핵심이다.!!

동적프로그래밍이 가능한 경우라면 동적프로그래밍으로 최소한의 계산으로 최대한의 속도를 내야한다.

 

 

package dp;

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


public class _14852{
    static int n;
    static long d[][] = new long[1000000][2];
    static long dp(int c){
        d[0][0] = 0;
        d[1][0] = 2;
        d[2][0] = 7;
        d[2][1] = 1;
        for(int i = 3 ; i <= c ; i++){
            d[i][1] = (d[i-1][1] + d[i - 3][0]) % 1000000007;
            d[i][0] = (2*d[i-1][0] + 3*d[i-2][0] + 2*d[i][1]) % 1000000007;
        }

        return d[c][0];
        
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        System.out.println(dp(n));

    }
}

 

 

참고 : https://www.youtube.com/watch?v=kYoKLm8BZtI&t=300s

동빈나의 동적프로그래밍 23강 2번째 문제를 강의보고 풀어보았습니다.

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study