[c++][BOJ][1932] 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

맨 위에서부터 내려왔을 때 , 가장 큰 점수를 획득하는 경우를 구하는 문제입니다.

 

반대로 생각하면 , 아래에서 맨 위로 올라갔을 때 가장 큰 점수를 구하면 됩니다.

 

특정 점 [ i , j ] 의 최대값은 [ i + 1][ j ] , [ i + 1 ][ j + 1 ] 중에 큰 수를 구해서 정하고,

[ i , j ] 가 [ 1 , 1 ]이 될 때까지 올리면 됩니다. 

#include <iostream>
using namespace std;

int arr[501][501] = {0};

int main(){
    int n;
    cin >> n;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            cin >> arr[i][j];
        }
    }
    
    for(int i=n-1; i>0; i--){
        for(int j=1; j<n; j++){
            arr[i][j] = arr[i][j] + max(arr[i+1][j] , arr[i+1][j+1]);
        }
    }
    
    cout << arr[1][1];
}