🖊️ 문제

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

---

🖊️ 풀이

해당 문제의 알고리즘은 https://youtu.be/0bqfTzpWySY 을 참고해서 풀었습니닷.

DP의 중요 포인트는
나만의 자료구조를 만들어서 이전 값을 저장해놓고 연산을 줄이는 방안이닷.

2차원 벡터 triangle을 따라서 나만의 자료구조.
이전 값들을 저장해놓을 vec을 만들었다.

vec에는 루프를 돌면서
상위 층에서부터 더해간다.
더해가면서 해당 과정에서의 최댓값을 저장해놓는다.

이 문제는 풀면서 주석에 메모를 하면서 풀었다.

한 번 계산할 때 비교군이 2개밖에 없다.
그래서 계산하고, vec에 저장해놓는다.
그래서 다음에는 계산할 때 비교군이 vec의 이전 층의 값이다.
그래서 이렇게 쭉쭉 해주면 됨!
비교군이 1개인 경우의 예외처리를 잘 해주면 큰 문제는 옶다 !

#include <string>
#include <vector>

using namespace std;

int vec[501][501];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int size = triangle.size();
    
    vec[0][0] = triangle[0][0];
    // vec[3][2] = vec[2][1] + triangle[3][2] or vec[2][2] + triangle[3][2]; 둘 중 더 큰 애로
    // vec의 기준 : first = i-1  / second = j - 1 && j (j-1 > 1)
    // 예외처리 
    // - j == 0 -> 무조건 [i-1][0]과 더하기
    // - j == 3 (맨 끝) -> 무조건 j-1과 더하기
    
    for(int i = 1 ; i < size ; i++) {
        for(int j = 0 ; j < i + 1 ; j++) {
            if (j == 0) 
                vec[i][j] = vec[i-1][j] + triangle[i][j];
            else if (j == i)
                vec[i][j] = vec[i-1][j-1] + triangle[i][j];
            else
                vec[i][j] = vec[i-1][j-1] > vec[i-1][j] ? 
                vec[i-1][j-1] + triangle[i][j] : vec[i-1][j] + triangle[i][j];
        }
    }
    
    int max = 0;
    for (int i = 0 ; i < size ; i++) {
        if (max <= vec[size-1][i])
            max = vec[size-1][i];
    }
    answer = max;
    return answer;
}