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

 

 

Code

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 501;
int dp[MAX][MAX];
int solution(vector<vector<int>> triangle) {
    int answer = 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(i==j){
                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 i=0;i<MAX;i++){
        for(int j=0;j<MAX;j++){
            answer = max(answer,dp[i][j]);
        }
    }
 
    return answer;
}