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

문제 링크

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

프로그래머스

 

 

코드 구현

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

using namespace std;

int solution(vector<vector<int>> triangle)
{
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));


    // dp 테이블 맨 아랫쪽 초기화
    for (int i = 0; i < n; ++i)
    {
        dp[n - 1][i] = triangle[n - 1][i];
    }

    // 아래부터 올라가면서 dp 테이블 채우기
    for (int i = n - 2; i >= 0; --i)
    {
        for (int j = 0; j <= i; ++j)
        {
            dp[i][j] = triangle[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }

    return dp[0][0];
}

 

 

해결 방법

---

• 거쳐간 숫자의 최댓값을 구하는 문제이기 때문에 아래에서 위로 올라가면서 가장 위의 [0][0] 값이 최댓값이 되도록 유도
• 삼각형의 i, j 위치까지 거쳐간 숫자의 합 중 최댓값을 dp[i][j]라고 하고 삼각형의 구성 요소의 값을 triangle[i][j]라고 했을 때, dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]가 된다.
• 아래에서 위로 올라가므로 결국 i, j = (0, 0)이 될 것이고 dp[0][0]이 곧 최댓값