[프로그래머스 문제풀이] 32. 정수 삼각형

개요

이 문제는 몇년전에 내가 풀다가 포기했던 기록이 남아있었다. 근데 지금은 동적계획법 문제를 푸는 방법을 알고나니 빠른 시간 내에 해결했다.

코드 설명

각 층마다 triagle의 크기와 저장하는 값의 크기가 동일하기 때문에 triagle의 데이터를 갱신하면서 풀었다.

각 층의 처음과 끝은 단순하게 윗층의 바로 위에 있는 값을 더하고
가운데 값들은 바로 위에 있는 두 값을 중 큰 수와 본인을 더한 값으로 갱신했다.

이렇게 맨 아랫층에 도달한다면 아랫층에는 최종적인 값들만 남아있다. 이 값 중 최댓값을 찾으면 된다.

🎉완성코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    for (size_t floor_index = 1; floor_index < triangle.size(); ++floor_index)
    {
        triangle[floor_index][0] = triangle[floor_index - 1][0] + triangle[floor_index][0];

        for (size_t j = 0; j < triangle[floor_index - 1].size() - 1; ++j)
            triangle[floor_index][j + 1] = max(triangle[floor_index - 1][j], triangle[floor_index - 1][j + 1]) + triangle[floor_index][j + 1];

        triangle[floor_index][floor_index] = triangle[floor_index - 1][floor_index - 1] + triangle[floor_index][floor_index];
    }

    int max_num = 0;
    for (int d : triangle[triangle.size() - 1])
        max_num = max(max_num, d);

    return max_num;
}

정수 삼각형 문제 링크