[백준] 정수 삼각형 1932번 (c++)

출처 : 1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

풀이 방법

삼각형을 위에서부터 내려오면서 자신의 인덱스가 자신이 속한 층내에서 i 번째라면 바로 위층의 i-1,i 번째 인덱스 중 큰 수를 더해주면서 가장 바닥까지 내려와 바닥중 가장 큰 수를 출력하면 된다

#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> triangle;
int N, ans;

int main() {
    cin >> N;
    triangle.resize(N);
    for (int i = 0;i < N;i++) {
        for (int k = 0;k < i+1;k++) {
            int num;
            cin >> num;
            triangle[i].push_back(num);
        }
    }
    for (int i = 1; i < N;i++) {
        for (int k = 0;k < i+1;k++) {
            if (k == 0) { // 인덱스가 0 이라면 무조건 위층의 0번인덱스만 더할 수 있다.
                triangle[i][k] += triangle[i-1][0];
            }
            else if (k == i) { // 인덱스가 마지막이라면 위층의 마지막 인덱스만 더할 수 있다.
                triangle[i][k] += triangle[i-1][i-1];
            }
            else { // 큰 수 더해주기 
                triangle[i][k] += max(triangle[i-1][k-1], triangle[i-1][k]);
            }
        }
    }

    sort(triangle[N-1].begin(), triangle[N-1].end());
    cout << triangle[N-1][N-1];
    return 0;
}