프로그래머스 Level3 - 정수 삼각형, C++

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

using namespace std;

int arr[501][501];

// 다음 외부 벡터에서 오른쪽 왼쪽 위치를 골라야 한다
// 인덱스가 같은게 왼쪽 1큰게 오른똑이다
// arr을 통해 dp

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    
    // 꼭짓점 값
    answer = arr[0][0] = triangle[0][0];
    
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0){
                arr[i][j] = arr[i-1][j] + triangle[i][j];
            }
            else if(j == i){
                arr[i][j] = arr[i-1][j-1] + triangle[i][j];
            }
            else {
                arr[i][j] = max(arr[i-1][j], arr[i-1][j-1]) + triangle[i][j];
            }
            
            answer = max(answer, arr[i][j]);
        }
    }
    return answer;
}

---

 이전에 이런 문제들을 많이 풀었기에 풀 수 있었던 문제입니다. arr 배열을 하나 더 만들어서 이곳에 삼각형 값들을 더하고 이 중에서 제일 큰 값을 점점 올리는 식입니다. 다른 사람들의 코드를 보니 기존의 배열 triangle을 이용해서 += 를 하는 방식으로 했는데 그 방식이 시간적으로, 공간적으로 더 나아 보입니다. 이후 개선의 여지가 있는 코드