[프로그래머스 lv 3 ] - 정수삼각형 (C++)

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

프로그래머스

 

 

 

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

using namespace std;

int solution(vector<vector<int>> triangle) {    
    int dp[500][500] = {};
    dp[0][0]=triangle[0][0];
    
    const int size = triangle.size();
    for(int i=1; i<size;i++)
    {
        for(int j=0; j<=i;j++)
        {
            dp[i][j]=triangle[i][j];
            
            const int Left = dp[i-1][j];
            const int Right = dp[i-1][j-1];
            if(j==0)  //제일 왼쪽
            {
                dp[i][j] += Left;
            }
            else if(j==triangle[i].size()-1) //제일 오른쪽
            {
                dp[i][j] += Right;
            }
            else
            {
                dp[i][j] += max(Left, Right);
            }          
        }
    }
    
    int answer = 0;    
    for(int i=0; i<triangle[size-1].size();i++)
    {
        answer = max(answer,dp[size-1][i]);    
    }

    return answer;
}