🌞문제

이 문제가 DP라고 생각 할 수 있는점은 문제를 풀면서 알 수 있었던 것 같다.
여태까지 계산했던 내용을 배열에 저장하고 그 배열을 다시 이용하는 부분에서 DP인 것을 알 수 있었다.

🌞접근법

이 문제에서의 핵심은 삼각형의 마지막 층의 원소의 개수들이 결과 배열의 크기가 된다는 점이었다.

위에서 아래로 내려오면서 거쳐 온 값들의 최댓값을 구하는 것이기 때문에 해당 층수의 어떠한 요소로 왔을 때의 최댓값은 한개이기 때문이다.

🌞풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int res[501];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    res[0] = triangle[0][0];
    
    for(int i=1;i<triangle.size();i++)
    {
        int tmp[501];
        int size = (sizeof(res)/sizeof(*res));
        copy(res, res+size, tmp);
        for(int j=0;j<triangle[i].size();j++)
        {
            if(j!=triangle[i].size()-1 && tmp[j]+triangle[i][j] > res[j]) res[j] = tmp[j]+triangle[i][j];
            if(j > 0 && tmp[j-1]+triangle[i][j] > res[j]) res[j] = tmp[j-1]+triangle[i][j];
        }
    }
    
    int max = -1;
    for(int i=0;i<500;i++)
    {
        if(res[i] > max) max=res[i];
    }
    answer = max;

    return answer;
}

/*

거쳐간 숫자의 합이 가장 큰 경우를 찾는다.
아래 칸으로 이동 시 대각선 방향으로 오른쪽 또는 왼쪽으로 이동 가능
7에 대해서 왼쪽 오른쪽
3에 대해서 왼쪽 오른쪽
8에 대해서 왼쪽 오른쪽
...
max값을 찾는다.

배열에다가 저장을 하는거지, 7

3의 입장에서는 7을 가져와야한다.
738 781 780
7382 7387 7814 7804
다음 레벨에 요소에 떨어지는 것들 중에서 가장 큰 값을 찾아서 select

*/