[백준 1932] 숫자삼각형

문제

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

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1줄까지 숫자 삼각형이 주어진다.

출력

첫째 줄에는 최대가 되는 합을 출력한다.

입력

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력

30

먼저 N을 입력받고 이차원배열에 숫자삼각형을 입력한다.

그리고 나서 윗층과 누적할 이차원배열이 필요하다. 크기는 숫자삼각형 입력받은 것과 동일하며 

두 번째줄부터 윗줄과 더하고 그 누적값을 가지고 있어야한다.

맨 왼쪽일 경우, 맨 오른쪽일 경우, 중간에 있을 경우가 있다.

여기서 맨 왼쪽, 오른쪽은 상관없지만 중간에 있을 경우 가장 큰 것을 찾아야 한다.

그러면 중간 값은 자기보다 위 줄의 좌, 우에서 큰 값을 찾아야한다.

즉 자신의 위치에서 대각선 , 우의 최대값을 가져오면 되는 문제이다.

소스

// //  main.cpp //  DP // //  Created by seungwoo on 2018. 3. 30.. //  Copyright © 2018년 seungwoo. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; int dp[502][502]; int a[502][502]; int main() {     int n;          cin>>n;          for(int i=1; i<=n; i++)     {         for(int j=1; j<=i; j++)             cin>>a[i][j];     }          for(int i=1; i<=n; i++)     {         for(int j=1; j<=i; j++)             dp[i][j] = a[i][j] +  max(dp[i-1][j],dp[i-1][j-1]);     }     int res = 0;     for (int i = 1; i <= n; i++)         res = max(res, dp[n][i]);     cout<<res;     return 0; }