Algorithm

[백준 1932] 숫자삼각형

승우승 2018. 3. 30. 23:56
반응형

문제

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;

}


 




반응형