[백준 / BOJ] C++ 1932 정수 삼각형

1932번: 정수 삼각형

 

문제

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

1932번: 정수 삼각형

 

 

풀이

삼각형의 가장 위에서 아래로 차례대로 더해 최댓값을 구하는 문제. dp를 사용해 풀었다.

 

삼각형의 어느 위치에서 합의 최댓값이 되려면 그 윗 층의 인접한 두 위치까지의 합 중 더 큰 곳에 해당 위치의 값을 더한 값이 된다. 이를 구현하면 끝인 문제다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<vector<int>> v(501, vector<int>(501, 0)), dp(501, vector<int>(501, 0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
      cin >> v[i][j];
  dp[0][0] = v[0][0];
  for (int i = 0; i < n - 1; i++)
    for (int j = 0; j <= i + 1; j++)
      dp[i + 1][j] = max(dp[i][j], dp[i][j - 1]) + v[i + 1][j];
  cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << '\n';
  return 0;
}