[Baekjoon] - 14단계 : 동적계획법 1

1. 피보나치 함수

#include <stdio.h>
 
void fibonacci(int N)
{
    int last, current, result;
    current=1, last = result = 0;
    int i;
    for (i = 0; i <=N; i++)
    {
        last = current;
        current = result;
        result = last + current;
    }
    printf("%d %d\n", last, current);
}
int main()
{
    int N,M;
    int i;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%d", &M);
        fibonacci(M);
    }
}

2. 신나는 함수 실행

#include <stdio.h>

int memo[101][101][101] = {0,};

int w(int a, int b, int c){
    
    if(a < 1 || b < 1 || c < 1) return 1;
    
    else if(a > 20 || b > 20 || c > 20) return memo[a][b][c] = w(20,20,20);
    
    //이미 값이 있으면 저장된 값만 불러오기
    else if(memo[a][b][c] != 0) return memo[a][b][c];
    
    //값이 0(값을 저장한 적 없으면) memo배열에 저장하고 반환
    else if(a < b && b < c)
        return memo[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    
    else
        return memo[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
}

int main(){
    int n1 = 0;
    int n2 = 0;
    int n3 = 0;
    
    
    while(scanf("%d %d %d",&n1,&n2,&n3)){
        if(n1 == -1 && n2 == -1 && n3 == -1) break;
        
        printf("w(%d, %d, %d) = %d\n",n1,n2,n3,w(n1,n2,n3));
    }
}

3. 01타일

#include <stdio.h>
#define div 15746

int main(){
    int n;
    scanf("%d",&n);
    
    int memo[1000001] = {0,};
    memo[1] = 1;
    memo[2] = 2;
    
    for(int i=3;i<=n;i++){
        memo[i] = (memo[i-2] +memo[i-1]) % div;
    }
    printf("%d",memo[n]);
}

4. 파도반 수열

#include <stdio.h>

long memo[101] = {0,};

long memoi(int n){//다른사람들은 f(n-5)+f(n-1) 로 하더라.
    if(n < 6) return memo[n];
    else if(memo[n] != 0) return memo[n];
    else return memo[n] = memoi(n-3) + memoi(n-2);
}

int main(){
    int t,n;
    scanf("%d",&t);
    
    memo[1] = memo[2] = memo[3] = 1;
    memo[4] = memo[5] = 2;
    for(int i=0;i<t;i++){
        scanf("%d",&n);
        printf("%ld\n",memoi(n));
    }
}

5. RGB거리

#include <stdio.h>

int getMin(int a, int b){
    return a < b ? a : b;
}
int main(){
    int t;
    scanf("%d",&t);
    
    int house[1001][4]={0,};//입력값 배열
    int cost[1001][4]={0,};//합쳐지는 비용 배열
    for(int i = 0;i<t;i++){
        scanf("%d %d %d",&house[i][0], &house[i][1], &house[i][2]);
    }
    
    cost[0][0] = house[0][0];
    cost[0][1] = house[0][1];
    cost[0][2] = house[0][2];
    
    for(int i=1;i<t;i++){
        cost[i][0] += (house[i][0] + getMin(cost[i-1][1],cost[i-1][2]));
        cost[i][1] += (house[i][1] + getMin(cost[i-1][0],cost[i-1][2]));
        cost[i][2] += (house[i][2] + getMin(cost[i-1][0],cost[i-1][1]));
    }
    
    int answer = getMin(cost[t-1][2],getMin(cost[t-1][0],cost[t-1][1]));
    
    printf("%d",answer);
}

요약

6. 정수 삼각형

#include <stdio.h>

int getMax(int a, int b){
    return a > b ? a : b;
}
int main(){
    int t=0;
    scanf("%d",&t);
    
    int tri[501][501] = {0,};
    int sum[501][501] = {0,};
    
    for(int i=0;i<t;i++){
        for(int j=0;j<i+1;j++){
            scanf("%d",&tri[i][j]);
        }
    }
    
    sum[0][0] = tri[0][0];
     
    for(int i=1;i<t;i++){
        for(int j=0;j<i+1;j++){
            if(j==0){
                sum[i][j] = tri[i][j] + sum[i-1][j];
            }
            else if(j==i){
                sum[i][j] = tri[i][j] + sum[i-1][j-1];
            }
            else{
                sum[i][j] = tri[i][j] + getMax(sum[i-1][j],sum[i-1][j-1]);
            }
        }
    }
    
    int max = 0;
    int index = t-1;
    for(int i=0;i<t;i++){
        max = getMax(sum[index][i], max);
    }
    
    printf("%d",max);
}

• 2번은 메모이제이션으로 주석설명.
• 4번은 long타입이어야한다.
• rgb를 끝내면 정수삼각형 문제가 쉬워진다.