[promgrammers] 정수 삼각형

문제 링크입니다

🚀 [정수 삼각형] Lv. 3 문제

다이나믹 프로그래밍을 사용해 문제를 쉽게 해결할 수 있다.

이전 알고스팟에서 배운 TRIPATHCNT 문제와 동일해 쉽게 풀 수 있었다. TRIPATHCNT

💎 전체 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int dp[501][501];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    N = triangle.size();
    dp[0][0] = triangle[0][0];
    // 맨왼쪽 줄과 맨오른쪽 줄을 먼저 전처리해준다.
    for(int i=0 ; i<N-1; i++){
        dp[i+1][0] = dp[i][0] + triangle[i+1][0];
        dp[i+1][triangle[i+1].size()-1] = dp[i][triangle[i].size()-1] + triangle[i+1][triangle[i+1].size()-1];
    }
    for(int i=2; i<N; i++){
        for(int j=1; j<triangle[i].size()-1; j++){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];    
        }
    }
    for(int i=0; i<N; i++){
        answer = max(answer, dp[N-1][i]);
    }
    return answer;
}