[프로그래머스] 정수 삼각형 (C++)

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

프로그래머스

DP 동적계획법

 

이런 정수 삼각형이 2차원 벡터 배열로 주어지고, 대각선 왼쪽 한칸 혹은 오른쪽 한칸으로만 이동하면서 내려갈 수 있다고 할 때, 거치는 수들의 합이 최대값을 반환하는 문제.

 

 

 

 

 

 

 

 

 

접근방법

2차원 배열을 똑같은걸 하나 복사해두고, 이걸 각 위치까지 오는데 거친 수들의 합의 최댓값을 저장해두는 용도로 사용한다. (accTri) = 최대누적트리라고 하겠다.

그리고 맨위에서 부터 맨 마지막 바로 전 줄까지 보면서, 내가 갈 수 있는 위치의 accTri 값을 갱신하면서 간다.

예를들어, 맨위의 7에서는 3과 8로 갈 수 있으니, 3 자리의 값을 10으로 갱신하고, 8자리의 값을 15로 갱신한다.

이때 각 위치의 오리지널 값을 따로 저장해두고 있어야 하므로 배열을 복사해서 사용해야 한다.

갱신할 때 규칙은, [r][c]가 현재 내 위치라고 할 때, 나(오지리널 값)를 더할 수 있는 위치인 [r+1][c] 와 [r+1][c+1] 의 최대누적트리의 값이, 나를 더했을 때와 더하지 않았을 때를 비교하여 더 큰 값으로 갱신한다. 

if (accTri[r+1][c] < accTri[r][c] + triangle[r+1][c])

이런 식이다.

이렇게 마지막 바로 전 줄 까지 보고 나면, 마지막 줄에는 해당 노드까지 도달하는데 거친 수들의 합 중 최댓값을 저장해두게 된다.

 

그러면 마지막에 마지막 줄 중 최댓값을 뽑아서 반환하면 된다.

 

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    vector<vector<int>> accTri(triangle.begin(), triangle.end());
    
    for(int r = 0 ; r < n-1 ; r++){
        for(int c = 0 ; c <= r ; c++){
            if(accTri[r+1][c] < accTri[r][c] + triangle[r+1][c]){
                accTri[r+1][c] = accTri[r][c] + triangle[r+1][c];
            }
            if(accTri[r+1][c+1] < accTri[r][c] + triangle[r+1][c+1]){
                accTri[r+1][c+1] = accTri[r][c] + triangle[r+1][c+1];
            }
        }
    }
    
    for(int i = 0 ; i < n; i++){
        if(answer < accTri[n-1][i]) {
            answer = accTri[n-1][i];
        }
    }
    return answer;
}

DP역시 존잼..