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

(6/26 - O)

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

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

 

생각보다 쉽게 풀려서 정말 기뻤던 문제!

 

 

구현

dp테이블을 이용하여 좌표마다 가질 수 있는 최댓값을 위에서 아래로 내려가면서 갱신해 준다. 가장 마지막 줄의 원소 값들 중 가장 큰 값을 리턴한다.

 

 

 

코드

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

using namespace std;

int dp[501][501];

int solution(vector<vector<int>> triangle) {
    int answer = 0;

    for (int i = 0; i < 501; i++) {
        fill(dp[i], dp[i] + 501, -1);
    }

    dp[0][0] = triangle[0][0];

    int i_size = triangle.size();
    for (int i = 1; i < i_size; i++) {
        int j_size = triangle[i].size();
        for (int j = 0; j < j_size; j++) {
            if(j - 1 >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + triangle[i][j]);
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + triangle[i][j]);
        }
    }
    
    answer = *max_element(dp[i_size - 1], dp[i_size - 1] + triangle[i_size - 1].size());

    return answer;
}

int main()
{
    vector<vector<int>> v;
    v.push_back({ 7 });
    v.push_back({ 3,8 });
    v.push_back({ 8,1,0 });
    v.push_back({ 2,7,4,4 });
    v.push_back({ 4,5,2,6,5 });

    solution(v);
}