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

문제

---

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

풀이

---

일정 패턴의 숫자 배열이 주어졌을 때, 맨 위에서 맨 아래까지 경로의 최대 합을 구하는 문제로, DP로 풀 수 있는 문제이다. 최대 합을 구하는 문제이므로, 순서대로 경로의 합을 더하고,위의 값 중 최대 값을 남겨 맨 아래에 도착했을 때의 가장 큰 수를 return한다.

#include <string>
#include <vector>

using namespace std;

int dp[10000][10000];

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

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

    for (int i = 1; i < triangle.size(); i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0)
            {
                dp[i][j] = dp[i - 1][0] + triangle[i][j];
            }

            else if (j == i)
            {
                dp[i][j] = dp[i - 1][i - 1] + triangle[i][j];
            }

            else
            {
                dp[i][j] = max(dp[i - 1][j - 1] + triangle[i][j], dp[i - 1][j] + triangle[i][j]);
            }
            
        }
    }

    for (int i = 1; i < triangle.size(); i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (answer < dp[i][j])
            {
                answer = dp[i][j];
            }
        }
    }

    return answer;
}