🐣 문제

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

🐥 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin >> N;
  int dp[501][501];
  int t[501][501];
  for(int i = 0; i < N; i++){
    for(int j = 0; j < i + 1; j++){
      cin >> t[i][j];  
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < i + 1; j++){
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + t[i][j];
    }
  }
  vector<int> v;
  for(int i = 0; i < N; i++){
    v.push_back(dp[N-1][i]);
  }

  sort(v.begin(), v.end(), greater<>());
  cout << v[0];
  
  return 0;
}