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

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

- 시간복잡도는 n = 삼각형의 높이라 할 때, n * (n-1) * (n-2) .. * 1 이므로 O(N^2)이다.

 

- 간단한 DP문제이다. DP문제는 반드시 점화식을 세워야 한다.

 

i를 꼭짓점부터의 해당 층의 상대적인 위치, j를 그 층에서의 요소의 인덱스라 할 때, 점화식은

 

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] (i, j = 0,1,...n)

 

단, 예외로 해당 층의 가장 첫 번째 요소인 경우와 가장 마지막 요소인 경우를 계산해야 한다.

 

해당 층의 가장 첫 번째 요소인 경우, dp[i][j] = dp[i-1][j] + triangle[i][j]

 

해당 층의 가장 마지막 요소인 경우, dp[i][j] = dp[i-1][j-1] + triangle[i][j]이 점화식이 된다.

 

- 모든 dp값을 구했다면, 정수 값 중에 음수는 없으므로 가장 마지막 층에 답이 존재할 것이므로, 마지막 층의 dp값을 순회하면서 최대값을 구하여 answer에 담아 return 해 주면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> triangle) {
    long long answer = 0;
    int height = triangle.size();
    long long dp[500][500];
    dp[0][0] = triangle[0][0];
    for(int i = 1; i < height; i++){
        for(int j = 0; j < triangle[i].size(); j++){
            if(j==0) dp[i][j] = dp[i-1][0] + triangle[i][j];
            else if(j==triangle[i].size()-1) dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            else dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
        }
    }
    answer = dp[height-1][0];
    for(int i = 1; i < triangle[height-1].size(); i++) {
        if(answer < dp[height-1][i]) answer = dp[height-1][i];
    }
    return answer;
}