[BOJ-1932]숫자삼각형

음.... DP 문제였다.

삼각형 맨 윗부분에서 시작해서 맨 아래 부분까지 도달할 때 각 인자끼리 더한 값이 제일 큰 값을 구하는 것이었다.

   1

  2 3

 4 5 6

인 모양으로 있다면 

2, 3은 1에서 값을 받을 수 있고, 인접한 곳에서 값을 얻어 올 수 있다. 

그러면 5의 경우에는 2, 3 에서 값을 얻어올 수 있는 경우가 된다 

     1

    2 3

   4 5 6

  7 8 9 10

인 경우에 8은 4 5 / 9는 5 6 에서 값을 얻어 올 수 있게 된다. 

각 양끝에서는 값이 내려오는 곳은 7<-4 / 10<-6 내려 올 수 있고 양 끝 값이 아닌 안쪽에 있는 값은 2가지 경우에서 값을 가져 올 수 있게 된다.

값을 내려 받을 때 그 중 최대 값만 얻어오면 된다. 

 

위 식이 만들어졌고 이에 따라 코드를 작성하였다. (M(a,b)은 둘(a,b) 중 최대값)

#include<cstdio>
const int MAX = 1111;
int dp[MAX][MAX];
// 0 =   0
// 1 =  0 1
// 2 = 0 1 2 
// 3 =0 1 2 3
// f(r,c) = max(dp(r,c)+f(r-1,c-1) , dp(r,c)+f(r-1,c)); 
int max2(int a, int b){
    return (a>b)?a:b;
}
int main(){
    int n; scanf("%d", &n);
    int result = 0;
    for(int lev = 0 ; lev < n ; lev++){
        for(int c = 0 ; c <= lev ; c++){
            scanf("%d", &dp[lev][c]);
            if(lev!=0 && c != 0){
                dp[lev][c] += max2(dp[lev-1][c-1] , dp[lev-1][c]);
            }else if(lev!= 0 && c == 0){
                dp[lev][c] += dp[lev-1][c];
            }
            if(result < dp[lev][c]) result = dp[lev][c];
        }
    }
    printf("%d", result);
    return 0;
}