프로그래머스 정수 삼각형

저번 문제와 같이, DP 분류의 프로그래머스 문제이다. 머리속에서 좀 많이 생각을 해봤는데, 저번에 풀었던 문제와 아주 유사하게 접근할 수 있을 것 같다. 저번에 풀었던 문제는 dp 배열의 폭이 정해져있다면, 이번 dp 배열은 높이가 1 늘어날때마다 폭도 1 늘어난다.

 

그리고, 문제 지도는 피라미드 모양으로 되어있는데 이것을 왼쪽으로 챡 붙인 직각삼각형으로 생각하는게 머리속에서 문제를 푸는데 훨씬 도움이 된다.

 

저번 내려가기 문제에서는 폭이 정해져있고, 밑으로 내려가면서 그 자리에서 가질 수 있는 최대값/최소값을 저장하고 있었다. 이번 문제에서는 최소값이 없는 반면, 옆으로 한칸씩 증가한다. 따라서 DP 배열은 N*N 크기를 가진다. (마지막 row의 경우 N크기 이므로.)

그 외에, 각 셀을 채워주는것은 그저 for 루프를 추가하기만 하면 된다.

현재 row 크기만큼 돌며, 가장 왼쪽과 오른쪽일때 값은 그냥 위에서 가져오면 되고, 중간의 값은 윗줄에 접하는 두 값 중 최대값만 가져와 현대 DP에 넣으면 된다.

 

루프를 다 돌고 나면, 마지막 줄에서 최대값을 취하면 우리가 원하는 값을 찾을 수 있다!

---

#include <string>
#include <vector>
long long dp[2][501];
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    dp[0][1] = triangle[0][0];
    for (int i = 2; i <= triangle.size(); i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                dp[1][j] = dp[0][j] + triangle[i-1][j-1];
            }
            else if (j < i)
            {
                dp[1][j] = max(dp[0][j-1] + triangle[i-1][j-1], dp[0][j] + triangle[i-1][j-1]);
            }
            else
            {
                dp[1][j] = dp[0][j - 1] + triangle[i-1][j-1];
            }
        }
        for (int j = 0; j <= i; j++)
            dp[0][j] = dp[1][j];
    }
    long long maxVal = -1;
    for (int i = 0; i <= triangle.size();i++)
    {
        if (maxVal < dp[0][i])
            maxVal = dp[0][i];
    }
    return maxVal;
}

저번에 풀었던 문제와 유사한것을 거의 바로 보게 되어 약간 기분이 좋다. 조금씩 밟을 수 있는 땅이 넓어지는 느낌은 늘 새롭고 짜릿하다. 아이 좋아.

 

오늘도 평온한 하루가 되길. 슨민.