[프로그래머스]동적계획법(Dynamic Programming) : 정수 삼각형 (level 3)(c++)

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

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

 

 

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

using namespace std;

const int MAX = 500;
int D[MAX + 1][MAX + 1];

int solution(vector<vector<int>> triangle) {

    int N = triangle.size();
    
    /*
           점화식 :
           D[i][j] = tri[i][j]로 올 수 있는 경로의 i - 1번째 최대값
                   + tri[i][j]
    */
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            D[i][j] = max(D[i - 1][j - 1], D[i - 1][j]) + triangle[i - 1][j - 1];
        }
    }

    // 최대값 구하기
    int max_sum = 0;
    for (int i = 1; i <= N; ++i)
    {
        max_sum = max(D[N][i] , max_sum);
    }

    return max_sum;
}

 

 

BOJ 1932 정수 삼각형 문제와 동일하다

다만 입력을 직접 받는게 아니라서,

위 풀이로 풀때에는 triangle 값을 더해줄때 인덱스를 한칸 뒤로 밀어줘야 한다.