백준 14852번: 타일 채우기3 ( DP 누적합 문제 => 최적화 필요 )

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

14852번: 타일 채우기 3

#include<iostream>
#include<stdio.h>

using namespace std;

int d[1000001];

int solution(int n){
    if(n == 0) return 1;
    if(n == 1) return 2;
    if(n == 2) return 7;
    if(d[n] != 0) return d[n];
    int result = 2 * solution(n-1) + 3 * solution(n-2);
    for(int i = 3; i <= n; i++){
        result += (2 * solution(n-i));
    }
    
    return d[n] = result % 1000000007 ;
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",solution(n));
}

위 코드의 시간 복잡도

solution(n)을 구할 때 시간             =>   1(상수 시간)

뒤에 for문에서 sum을 구하는 과정   =>   n

 

solution()은 재귀 호출 함수이므로 총 n-1번 호출할 것이다. 그러므로 solution(n)을 구하는데 드는 시간은
1 * n 으로 n만큼 걸린다.

 

정리하면 solution()을 구할 때 시간 * 뒤에 for문에서 sum을 구하는 과정 = n * n  = O(n^2)

 

 

처음에는 위처럼 작성해서 제출했다. 하지만 시간 초과가 나왔다.

그 이유는 문제에서 N의 범위가 1~1,000,000 이었기 때문에 위의 코드로는 1000000^2 로 매우 큰 시간이 걸려서
시간 초과가 발생하기 때문이다.

 

그래서 sum을 구해주는 부분도 dp 테이블에 저장해서 매번 n번을 더하는 것이 아닌 더한 값을 dp 테이블에 저장
해두고 사용하도록 구현한다면 O(N)의 시간복잡도로 구현할 수 있다. 

 

즉, X[i] = sum( solution(i-1) + solution(i-2) + ... solution(0) ) 을 저장해 둔다면 그 다음 번에 X[i+1]을 구할 때는
저장되어 있는 값을 한 번 가져오기만 하면 도므로 O(1)만큼밖에 안 걸리기 때문이다. 그러므로 dp 이차원 배열을
이용해 구현하면 된다.

 

이게 바로 누적합을 저장해두는 누적합 문제 유형이다. ( 최적화를 필요로하는 심화된 dp 문제에 종종 나온다 )

 

 

정답 구현 

dp를 하나 더 만들어 sum을 저장해두자.

새로 만든 dp에 넣어야 할 값은 sum이다.

점화식

위 점화식에서 뒤에 2로 묶여있는 부분인 ( DP(n-3) + ... + DP(1) + DP(0) ) 를 새로 만든 dp에 넣어주는 것이 목표다.

실제로는 저 값을 2로 묶어줬으므로 DP[n][1]에 나중에 2를 곱해줘야 한다.

 

그러기 위해서 dp 이차원 배열을 만든다면

DP[n][0] => 길이가 2 x n일 때의 타일을 채우는 경우의 수가 들어감 

DP[n][1] =>  (solution(n-3) + ... + solution(1) + solution(0) ) 의 결과 sum 값이 들어감

 

위의 DP[n][1]을 다르게 보면 밑에처럼 볼 수 있다.

solution(n-3) + solution(n-2) + ... solution(0)
= { solution(n-3) } + { solution(n-2) + ... solution(0) }

 

즉, DP[n][1] = { DP[N-3][0] } + { DP[n-1][1] } 이 된다. 

 

그러므로
DP[n][1] = DP[n-3][0] + DP[n-1][1];

DP[n][0] = 3 * DP[n-2][0] + 2 * DP[n-1][0] + 2 * DP[n][1]; 

 

 

정답 코드     

#include<iostream>
#include<stdio.h>

using namespace std;

long dp[1000001][2];

long solution(int n){
    dp[0][0] = 1;
    dp[1][0] = 2;
    dp[2][0] = 7;
    dp[2][1] = 0;
    
    if(dp[n][0] != 0) return dp[n][0];
    
    for(int i = 3; i <= n; i++){
        dp[i][1] = (dp[i-3][0] + dp[i-1][1]) % 1000000007;
        dp[i][0] = (3 * dp[i-2][0] + 2 * dp[i-1][0] + 2 * dp[i][1]) % 1000000007;
    }

    return dp[n][0];
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%ld",solution(n));
}