[1932] 정수 삼각형

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

1932번: 정수 삼각형

2차원 dp 문제이다.

dp[i][j]=i행에서 j번째 수를 선택할때의 최대값으로 채워주었고, O(n^2)만에 해결할 수 있다.

 

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[501][501], dp[501][501];
int main(void) {
    int n, i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
        }
    }
    int max = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            if (max < dp[i][j])
                max = dp[i][j];
    printf("%d", max);
    return 0;
}