1932번 정수 삼각형

크기 N인 정수 삼각형을 입력받아 맨 위층에서 N층까지 내려가면서 수를 더하고 맨 아래층에 도달했을 때 나올 수 있는 최대 값을 구하는 문제

 

나는 밑에서부터 큰 값을 정해 위층에 더해주는 방식으로 맨 위층까지 올라가 최대값을 구하였다

 

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

#define MAX 501

using namespace std;

//vector<int> tri[MAX];
int tri[MAX][MAX];
int value[MAX][MAX];

void dp(int number){
    
    for(int n=number;n>1;n--){
        for(int k=number;k>1;k--){
            tri[n-2][k-2] = tri[n-2][k-2] + max(tri[n-1][k-2], tri[n-1][k-1]); // 점화식 아래서부터 위로
        }
    }
}

int main(){
    int number;
    cin >> number;
    
//    for(int i=0; i<number; i++){
//        for(int j=number-1-i;j<number;j++){
//            int n;
//            cin >> n;
//            tri[i].push_back(n);
//        }
//    }

//  ------------------------------- 벡터로 풀었을때 틀린 이유는 뭘까?
    
    for(int i=0; i<number; i++){
        for(int j=0;j<i+1; j++){
            int n;
            cin >> n;
            tri[i][j] = n;
        }
    }
//    for(int i=0; i<number; i++){
//        for(int j=0;j<i+1; j++){
//            cout << tri[i][j] << " ";
//        }
//        cout << endl;
//    }
    
    dp(number);
    
    cout << tri[0][0] << endl;
//    cout << tri[1][0] << endl;
}