백준 1932 - 정수 삼각형

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

1932번: 정수 삼각형

문제 설명

---

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때,

이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

 

접근 방법

---

DP 로 접근하며, 각층에서 최대가 되는 숫자를 저장해 나간다. 이후 마지막 자식 트리에서 최대값을 찾으면 된다.

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,count=0;
int tri[501][501];
int maxi[501][501];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cin>>tri[i][j];
        }
    }
    maxi[0][0]=tri[0][0];
    for(int i=1;i<n;i++){
        for(int j=0;j<=i;j++){
            if(j==0) maxi[i][j]=maxi[i-1][j]+tri[i][j];
            else if(j==i) maxi[i][j]=maxi[i-1][j-1]+tri[i][j];
            else maxi[i][j]=max(maxi[i-1][j-1],maxi[i-1][j])+tri[i][j];
        }
    }
    sort(maxi[n-1],maxi[n-1]+n);
    cout<<maxi[n-1][n-1];
    return 0;
}

funny algorithm T.T;;;