[백준 1932] 정수 삼각형

1932번: 정수 삼각형 (acmicpc.net)

 

 

내 풀이

#include <bits/stdc++.h>
using namespace std;

int n;

int a[505][505], d[505][505];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n;
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      cin >> a[i][j];
  
   d[1][1]=a[1][1];
    
    for(int i=2;i<=n;i++)
    {
       for(int j = 1; j <= i; ++j)
       {
           d[i][j]=max(d[i-1][j],d[i-1][j-1])+ a[i][j];
          
        
       }
    }
 
    
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < d[n][i])
            max = d[n][i];
    }
    
    cout << max << '\n';
    
    return 0;
}