[백준] 1932 정수 삼각형(C++)

 

문제 URL:

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

1932번: 정수 삼각형

이 문제는 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하는 문제로,

삼각형의 제일 밑에서 두 수를 비교하면서 둘 중에 큰 값을 위에 있는 값에 누적시키면 마지막 배열[0][0]에 원하는 결과가 나오게 된다. 

---

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

int n;
int dp[500][500];

int main() {
  cin >> n;

  for (int i = 0; i < n; i++) 
    for (int j = 0; j < i+1; j++) 
      cin >> dp[i][j];

  for(int i = n-1; i >= 1;i--)
    for(int j=0;j<i;j++)
      dp[i-1][j] += max(dp[i][j],dp[i][j+1]);

  cout << dp[0][0];

  return 0;
}