다이나믹 프로그래밍 - 기본, 타일링

하나의 문제를 단 한번만 풀게 하는것

 

가정1. 큰 문제를 작은 문제로 나눌 수 있다.

가정2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

피보나치 수열의 예제

#include <stdio.h>

int dp(int x) {
    if(x ==1) return 1;
    if(x ==2) return 1;
    return p(x -1) + dp(x -2);
}

int main(void){
    printf("%d", dp(40));
}

#include <stdio.h>

int d[100];

int dp(int x) {
    if(x ==1) return 1;
    if(x ==2) return 1;
    if(d[x] !=0) return d[x];
    return d[x] = dp(x -1) + dp(x -2);
}

int main(void){
    printf("%d", dp(40));
}

 

이미 구한 값을 배열에 저장하여 그 값을 불러 냄

 

타일링

1.백준 11726

 - 점화식을 세운다

d[x] = d[x-1] + d[x-2]

x=1 일때 경우의 수 : 1

x=2 일때 경우의 수 : 2

#include <stdio.h>

int d[1001];

int dp(int x){
    if(x ==1) return 1;
    if(x ==2) return 2;
    if(d[x]!=0) return d[x];
    return d[x] = (dp(x - 1) +dp(x - 2)) % 10007;
}

int main(void){
    int x;
    scanf("%d", &x);
    printf("%d", dp(x));
}

 

2.백준 11727

d[x] = d[x-1] + 2*d[x-2]

x=1 일때 경우의 수 : 1

x=2 일때 경우의 수 : 3

#include <stdio.h>

int d[1001];

int dp(int x){
    if(x ==1) return 1;
    if(x ==2) return 3;
    if(d[x]!=0) return d[x];
    return d[x] = (dp(x - 1) +2 *dp(x - 2)) % 10007;
}

int main(void){
    int x;
    scanf("%d", &x);
    printf("%d", dp(x));
}

 

3.백준 2133

d[x] = 3*d[x-2] + 2*d[x-2] +2*d[x-4]+....2*d[0]

x=1 일때 경우의 수 : 0

x=2 일때 경우의 수 : 3

점화식을 세울 때 그 식에 예외는 없는지 확인한다. 

#include <stdio.h>


int d[1001];

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

int main(void){
    int x;
    scanf("%d", &x);
    printf("%d", dp(x));
    
}

 

3.백준 14852

x=1 일때 경우의 수 : 2

x=2 일때 경우의 수 : 3

--------------------------

x=3 일때 경우의 수 : 2

x=4 일때 경우의 수 : 2

.....

 

d[x] = 3*d[x-2] + 2*d[x-1] + (d[x-3]*2 + d[n-4]*2 ....2*d[0])

--------------------------

d[x] = d[x-1]*2 + d[x-2]*3 + (d[x-3]*2 + d[x-4]*2 + ....d[0]*2)

 

#include <stdio.h>


int d[1000001];

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

int main(void){
    int x;
    scanf("%d", &x);
    printf("%d", dp(x));
    
}

 

시간 초과 발생 = 효율적이지 않은 알고리즘임

2차원 dp 기법을 사용하여 해결 할 수 있다.

 

#include <stdio.h>


long long int d[1000001][2];

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

int main(void){
    int x;
    scanf("%d", &x);
    printf("%lld", dp(x));
    return 0;
}

 

dp기법을 사용할 때 배열을 이용해 그 값들을 저장하는 방법을 잘 숙지 하고 더 나아가서 2차원 dp의 개념과 사용법을 숙지 할 필요가 있음.

또한 점화식을 제대로 작성하는 방법과 종료조건의 수를 수학적으로 잘 고려해야 할 것으로 보임.