[백준 1932] 정수 삼각형, C++

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

1932번: 정수 삼각형

 본 문제는 1994 International Olympiad in Informatics 1번 문제다.

<크기가 5인 정수 삼각형>

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 선택된 수의 합이 최대가 되는 값을 구하는 문제다. 위 층에서 아래층으로 더했을 때 큰 값을 선택하는 방법보다. 아래층에서 위층 중 어떤 수를 더했을 때, 값이 커지는 가를 찾는 것이 코딩하기 쉽다. 즉, 2층 첫 번째 숫자 3과 3층의 8, 1을 더하는 것보다. 3층의 두 번째 숫자 1과 2층의 3과 8중 1과 더해서 큰 값을 1에 저장하는 것이다. 따라서, (실제 입력은 2차원 배열이다.) d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j] 계산한다. 이때, 각 층의 바깥쪽 숫자는 계산할 방법이 1가지 이므로 각각 따로 예외처리를 한다.

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int d[500][500];
int a[500][500];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    d[0][0] = a[0][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) d[i][j] = d[i-1][j] + a[i][j];
            else if (j == i) d[i][j] = d[i-1][j-1] + a[i][j];
            else d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (ans < d[n-1][i]) ans = d[n-1][i];
    }
    printf("%d", ans);
}