[c++]정수 삼각형

출처:프로그래머스

문제 설명

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

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

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

문제풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    
    for(int i = n-2; i >= 0; i--){ //끝에서 두번째 줄부터 더하기 시작
        for(int j = 0; j < triangle[i].size(); j++){
        	//현재 층 값을 아래층 두값 중 큰 값과 합을 구하기
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]); 
        }
    }
    //결국 마지막에 꼭대기값이 최대 합
    answer = triangle[0][0];
    return answer;
}

하단에서 최댓값을 계산하여 누적해 올라가는 방식으로 DP를 이용하였다. DP에서는 이미 계산한 값을 재사용할 수있어서, 같은 경로를 여러번 계산하지 않고도 결과를 구해낼 수 있다.