프로그래머스 - 정수 삼각형(Lv.3)

문제풀이

• 전형적인 동적계획법 문제이다.
• Triangle 각 지점으로 도달하는 방법 중 합이 최대가 되는 경우를 dp 배열에 담는다.
• 즉, dp[height][idx]는 height 높이의 idx에 위치한 지점까지 도달하는 경로 중 숫자의 합이 가장 큰 결과가 담긴다.
• 삼각형의 좌측 끝은 항상 dp[height-1][idx]로 부터 들어오고, 우측 끝은 dp[height-1][idx-1]로 부터 들어온다.
• 중간에 위치한 지점은 양쪽에서 다 받을 수 있으므로 그 중 큰 값을 선택한 후 현재 지점의 값을 더해준다.

구현(All Pass)

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

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    
    vector<vector<int>> dp(n, vector<int>(n,0));
    dp[0][0] = triangle[0][0];
    
    for(int height=1; height<n; height++){
        for(int idx=0; idx<triangle[height].size(); idx++){
            if(idx==0) // 왼쪽 끝에 위치한 경우
                dp[height][idx] = dp[height-1][idx];
            else if(idx==triangle[height].size()-1) // 오른쪽 끝에 위치한 경우
                dp[height][idx] = dp[height-1][idx-1];
            else // 중간에 위치한 경우
                dp[height][idx] = max(dp[height-1][idx], dp[height-1][idx-1]);
            dp[height][idx] += triangle[height][idx];
            
            // Debugging
            // cout << dp[height][idx] << " ";
        }
    }
    
    
    answer = dp[n-1][0];
    for(int i=1; i<triangle[n-1].size(); i++){
        answer = answer < dp[n-1][i] ? dp[n-1][i] : answer;
    }
    
    return answer;
}