[Programmers] 정수 삼각형 (C++)

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

프로그래머스

걸린 시간 : 10분

---

알고리즘

대표적인 DP 문제이다. 거쳐가는 숫자들을 더해서 저장해놓는 memo 배열을 채워가며, memo의 마지막 열 값들 중 최댓값을 리턴한다.

정답 코드

#include <string>
#include <vector>

using namespace std;

int memo[501][501];

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