정수 삼각형 풀이

프로그래머스 정수 삼각형 풀이

문제설명

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

삼각형 높이 ≤ 500

정수 < 10,000

정답의 최댓값은 ≤ 5000000 이므로 INT 로 충분하다.

해결과정

흔한? DP 문제로, DP[i][j] = max(DP[i-1][j], DP[i-1][j-1]) + 해당위치의 값으로 계산하면 된다. 자세하게는 위에서 아래로 DP를 처리하면서, 해당 층의 최댓값은 자신에게 올 수 있는 위층의 값 중 큰값과 자신의 값을 더하면된다. 만약 가장 왼쪽과 오른쪽, 삼각형의 왼쪽변과 오른쪽 변의 위치라면 자신에게 올 수 있는 위층은 하나이다. 하지만 중간에 위치하면 2개의 위치에서 자신의 층으로 올 수 있어, 위와 같은 점화식으로 해결할 수 있다.

소스코드

#include <string>
#include <vector>

using namespace std;
int dp[500][500];
int solution(vector<vector<int>> triangle) {
    int h = triangle.size();
    
    for(int i = 0; i<h;i++){
        for(int j = 0; j< triangle[i].size();j++){
            dp[i][j] = triangle[i][j];
        }
    }
    
    for(int i = 1; i<h;i++){
        dp[i][0] += dp[i-1][0];
        dp[i][i] += dp[i-1][i-1];
        for(int j = 1; j<i;j++){
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]);
        }
    }
    int ans = 0;
    for(int i = 0; i<h;i++){
        ans = max(dp[h-1][i], ans);
    }
    
    return ans;
}