[고급-6] 동적 테이블의 응용1

학습목표 : 

주어진 문제를 동적테이블을 활용하여 해결할 수 있다.

재귀함수와 반복문으로 동적테이블을 적용할 수 있다.

1. 동적테이블의 응용1

(1) 광석수집

맵이 주어졌을 때, 왼쪽 맨 위의 SCV가 오른쪽 맨 아래의 도착점까지 아래로, 혹은 오른쪽으로만 이동해서 최대의 광석을 구해야 한다.

<방법 1> 전체탐색.

모든 경로를 탐색한다. 무조건 정답을 찾을 수 있지만 비효율적.

<방법 2> 동적테이블 이용

#include <stdio.h>
 
int n, m, A[210][210], DT[210][210];
 
int max(int a, int b){
    return a>b? a : b;
}
 
int solve(int a, int b){
    if(DT[a][b] == 0){ // DT[a][b]인 경우가 처음일때는 계산하고,
        if(a==n&&b==m)
            DT[a][b]=A[a][b];
        else if(a>n || b>m)
            DT[a][b]=0;
        else
            DT[a][b]=max(solve(a+1, b), solve(a, b+1))+A[a][b];
    }
    return DT[a][b]; //아니라면 DT[a][b]를 불러옵니다.
}
 
int main(){
    int i, j;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; ++i){
        for(j=1; j<=m; ++j){
            scanf("%d", &A[i][j]);
        }
    }
    printf("%d\n", solve(1, 1));
    return 0;
}