동적 계획법 응용 : 정수 삼각형

∙문제 해결 방법

- 정수 삼각형을 직각 삼각형 형태로 표현할 경우, 임의의 좌표 (x, y)에 이동하기 위해서는 (x - 1, y -1) 또는 (x, y - 1)좌표를 거쳐야한다.

- 임의의 좌표 (x, y)에서의 삼각형 정수 값을 tri(x, y)라고 하고, 꼭대기 좌표에서 (x, y)까지 이동할 때의 정수 합의 최댓값을 dp(x, y)라고 할 경우 아래의 식이 성립된다.

 

- 꼭대기 좌표부터 시작하여 왼쪽에서 오른쪽으로 위에서 아래 방향으로 dp(x, y) 값을 계산하고, 최종적으로 삼각형 바닥에서 dp(x, y)의 최댓값 구한다.

 

∙ 정수 삼각형 문제의 솔루션 함수의 예

int solution(vector<vector<int>> triangle)
{
    vector<vector<int>> dp = triangle;

    int n = triangle.size();

    for (int y = 1; y < n; y++) {
        for (int x = 0; x <= y; x++) {
            if (x == 0)
                dp[y][x] = dp[y - 1][x] + triangle[y][x];
            else if (x == y)
                dp[y][x] = dp[y - 1][x - 1] + triangle[y][x];
            else
                dp[y][x] = max(dp[y - 1][x - 1], dp[y - 1][x]) + triangle[y][x];
        }
    }

    return *max_element(dp[n - 1].begin(), dp[n - 1].end());
}

 

- 실행 코드

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

using namespace std;

int solution(vector<vector<int>> triangle)
{
    vector<vector<int>> dp = triangle;

    int n = triangle.size();

    for (int y = 1; y < n; y++) {
        for (int x = 0; x <= y; x++) {
            if (x == 0)
                dp[y][x] = dp[y - 1][x] + triangle[y][x];
            else if (x == y)
                dp[y][x] = dp[y - 1][x - 1] + triangle[y][x];
            else
                dp[y][x] = max(dp[y - 1][x - 1], dp[y - 1][x]) + triangle[y][x];
        }
    }

    return *max_element(dp[n - 1].begin(), dp[n - 1].end());
}

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

    cout << solution(tri) << endl;
}