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

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

코딩테스트 연습 - 정수 삼각형 | 프로그래머스

삼각형을 타고 내려오면서 가장 큰 경로 값을 가져올 경우를 찾는 문제였다.

기본적인 DP로, 이전 경로에서 가장 큰 값에다 현재 경로 중 가장 큰 값을 더해주는 방식으로 경로를 확장해나가면서 해결할 수 있었다.

 

단, 삼각형의 둘레변 부분에서는 무조건 둘레변에서만 내려올 수 있으므로 이 부분들은 예외적으로 따로 처리해줬다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> path = triangle;

    // DP 이전 레벨까지의 최고 값을 갱신한다
    for(int i=1;i<path.size();i++){
        // 시작점은 무조건 바로 위 중앙값
        path[i][0] += path[i-1][0]; 
        for(int j=1;j<i;j++){
            path[i][j] += max(path[i-1][j], path[i-1][j-1]); // 최대값
        }
        // 끝점은 무조건 바로 끝값
        path[i][i] += path[i-1][i-1]; 
    }
    return *max_element(path[path.size()-1].begin(),path[path.size()-1].end() );
}