[프로그래머스] 정수 삼각형

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

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

Level 3이라고 적혀있지만 Level 3이 아닌 듯 하다.

문제에서 안내된대로 폭포수 같이 삼각형의 꼭대기에서부터 바닥까지 탐색하면서 최대값을 찾으면 된다.

DP를 활용하면 되는데, 어떤 부모(왼쪽? 오른쪽?)의 값을 가져오는 것이 이득인지 따지면 된다.

어차피 그 다음의 child들은 grandparent와 전혀 무관하기 때문이다.

그래서 Level 0을 제외한 Level 1 ~ Level.last까지 왼쪽과 오른쪽 중 큰 값을 가져오도록 한다.

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

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