[Programmers] Level 3 : 정수 삼각형

프로그래머스

전형적인 DP 문제이다.
제일 위에 있는 꼭짓점부터 가장 밑변까지 이동할때 얻을 수 있는 최댓값을 구해야 한다. 이를 삼각형 모습 그대로 본다면 굉장히 구현하기가 귀찮아진다. 그래서 어떻게 하면 쉽게 해결할 수 있을지 고민을 해보자.

이 그림에서 7을 잡고 쭉 잡아 왼쪽에 붙힌다고 생각해보자. 그러면 값은 아래와 같이 변한다.

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

이제 우리가 알고싶은 갚은 매우 간단하게 계산할 수 있다. 각 위치에 도달하기 위해서는 바로 자신의 위 혹은 왼쪽 대각선에서 내려올 수 있기 때문이다. 이를 누적합 + DP로 계산하면 아래와 같은 점화식을 얻을 수 있다.

DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + triangle[i][j]

이제 2중 for문을 돌면서 DP[i][j]의 최댓값을 구하면 O(N^2) 이내에 간단히 해결해낼 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int DP[510][510];

int solution(vector<vector<int>> triangles) {
    int answer = 0;
    DP[0][0] = triangles[0][0];
    for(int i=1; i<triangles.size(); i++) {
        vector<int> triangle = triangles[i];
        for(int j=0; j<triangle.size(); j++) {
            DP[i][j] = DP[i-1][j];
            if(j != 0) {
                DP[i][j] = max(DP[i][j], DP[i-1][j-1]);             
            }
            DP[i][j] += triangle[j];
            answer = max(answer, DP[i][j]);
        }
    }
    return answer;
}