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

📝 정수 삼각형

문제 설명

정수 삼각형

해결 방법

정수 삼각형을 직각 삼각형 형태로 표현을 해서, 임의의 좌표 (x, y)에 이동하기 위해서 (x, y -1) 또는 (x -1 , y - 1)을 거쳐야 한다.
임의의 좌표 (x, y)에서의 삼각형 정수 값을 tri(x, y)라고 하고, 꼭대기 좌표에서 (x, y)까지 이동할 때의 정수 합의 최댓값을 dp(x, y)라고 할 경우, 다음 식이 성립한다.
dp(x, y) = max(dp(x - 1, y - 1), dp(x, y - 1)) + tri(x, y)
dp(0, 0) = tri(0, 0)
꼭대기 좌표부터 시작하여 왼쪽에서 오른쪽으로, 위에서 아래 방향으로 dp(x, y) 값을 계산하고, 최종적으로 삼각형 바닥에서 dp(x, y)의 최댓값을 구한다.

💻소스코드

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

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> dp = triangle;
    
    int n = triangle.size();
    
    // y = 1 부터 시작: (0, 0)에서의 dp 값은 변경하지 않음 dp(0, 0) = tri(0, 0)
    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], dp[y - 1][x - 1]) + triangle[y][x];
        }
        // dp 벡터 맨 마지막행에서 최댓값을 찾음
        answer = *max_element(dp[n - 1].begin(), dp[n - 1].end());
    }
    
    return answer;
}