[백준] 1932.cpp : 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

• 임의의 정수들 중 각자 위치의 최댓값은, 연결된 부모 2개 값들 중 최댓값 + 자신의 값 이 된다.
• 첫 줄 부터 자기 위치의 최댓값을 갱신하면서 n 번째 줄 까지 내려가면, n 번째 줄에는 가능한 모든 최댓값들이 들어가게 된다.
• 다만 양쪽 끝 위치는 부모가 1개씩밖에 없기 때문에 따로 처리해야 하지만, 0 이 있다고 생각함으로써 똑같이 처리할 수 있다.
• 1차원 배열로 부모 자식 간의 연결 관계를 깔끔하게 처리하는 인덱싱 방법이 있다면 메모리를 더 효율적으로 사용할 수 있겠다.

---

#include <iostream>
#include <algorithm>

using namespace std;

int n, temp, _max;
int data[500][500];                     // 맨 왼쪽과 맨 오른쪽 역시 부모 값을 0 으로 줌

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;

    for(int idx = 1 ; idx <= n ; idx++)
    {
        for(int i = 1 ; i <= idx ; i++)
        {
            cin >> temp;
            data[idx][i] = max(data[idx-1][i-1], data[idx-1][i]) + temp;    // 자기 위의 두 값들 중 최댓값을 골라서 더해줌
            if(data[idx][i] > _max) _max = data[idx][i];                    // 최댓값 갱신
        }
    }
    cout << _max << endl;
}