BOJ : 1932 숫자삼각형

문제 : https://www.acmicpc.net/problem/1932

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번

• PKU Judge Online
• Sphere Online Judge

DP(다이나믹 프로그래밍)로 해결했다.

삼각형 꼭대기 값을 아래 행에 더해주며 최대값을 저장해 마지막에 출력한다.

#include <algorithm>
#include <cstdio>
using namespace std;

int N ,max_sum=0;;
int num[505][505];
int sum[505][505]={0,};
int main(){
    scanf("%d",&N);
    scanf("%d",&num[0][0]);
    sum[0][0] = num[0][0];
    max_sum = 0;
    for(int i=1;i<N;i++){
        for(int j=0;j<=i;j++){
            scanf("%d",&num[i][j]);
            if(j==0) {
                sum[i][0]=num[i][0]+sum[i-1][0];
                if(sum[i][0] > max_sum) max_sum = sum[i][0];
            }
            else if(j==i) {
                sum[i][j]=num[i][j]+sum[i-1][j-1];
                if(sum[i][j] > max_sum) max_sum = sum[i][j];
            }
            else {
                sum[i][j] = num[i][j] + max(sum[i-1][j-1], sum[i-1][j]);
                if(sum[i][j] > max_sum) max_sum = sum[i][j];
            }
        }
    }
    
    printf("%d",max_sum);
}