정수 삼각형

문제 링크

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

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

 

문제 풀이

 

문제 풀이 코드

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

using namespace std;

int dp[500][500]={0,};

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