(백준 알고리즘 문제풀이) 1932번 정수삼각형

문제

어떻게 접근할 것인가

이 문제는 디피로 풀 수 있는 문제이다.

맨 꼭대기 층부터 각 위치에서 두방향으로 더해서 다음 층의 값을 업데이트 한다.

코드

#include <cstdio>
int sum[501][501], tree[501][501];
int main(){
    int n, M = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            scanf("%d", &tree[i][j]);
        }
    }
    sum[0][0] = tree[0][0];
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j <= i; j++){
            if(sum[i+1][j] < sum[i][j] + tree[i+1][j])sum[i+1][j] = sum[i][j] + tree[i+1][j];
            if(sum[i+1][j+1] < sum[i][j] + tree[i+1][j+1])sum[i+1][j+1] = sum[i][j] + tree[i+1][j+1];
        }
    }
    for(int i = 0; i < n; i++){
        if(sum[n-1][i] > M) M = sum[n-1][i];
    }
    printf("%d", M);

}

느낀점

쉽죠잉