프로그래머스 : 정수 삼각형

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

삼각형 각 높이의 양 끝에 있는 값은 바로 위에 있는 경로로만 내려올 수 있습니다.

중앙에 있는 값은, 바로 위의 좌우 두개의 경로로만 내려올 수 있습니다.

이를 이용하여 각 위치를 지나갈 때 경로의 최댓값을 계속 업데이트해주었습니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int height = triangle.size();
    for(int i=1; i<height; i++) {
        triangle[i][0] += triangle[i-1][0];
        int size = triangle[i].size();
        for(int j=1; j < size - 1; j++) {
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]);
        }
        triangle[i][size-1] += triangle[i-1][size-2];
    }
    for(int i=0; i<triangle[height-1].size(); i++) {
        answer = max(answer, triangle[height-1][i]);
    }
    return answer;
}