[acmicpc.net] 1932 숫자삼각형

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

문제 내용

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 99 이하이다.

소스코드

#include <iostream>
using namespace std;
 
int main() {
    int n, *arr, *results, size;
    cin >> n;
    size = n*(n+1)/2;
    arr = new int[size];
    results = new int[n];
    for(int i=0; i<size; i++)
        cin >> arr[i];
    for(int i=0; i<n; i++)
        results[i] = arr[i+n*(n-1)/2];
     
    for(int h=n-1; h > 0; h--){// node height.(root node height=1)
        int start = h*(h-1)/2;
        for(int i=0; i<h; i++){
            results[i] = arr[start+i] + max(results[i], results[i+1]);
        }
    }
    cout << results[0];
    return 0;
}