1932번: 정수 삼각형

1932번: 정수 삼각형

사용 언어: C++

 

문제 요약

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

  위 그림은 크기가 5인 정수 삼각형의 한 모습이다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
• 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

풀이

문제 예시를 보면 위에서 아래로 가는 그리디 방식은 안된다 -> 전체합이 최대값이 된다는 보장이 없음.

그래서 아래에서 위로 올라가는 Bottom-Up DP 방식을 채택해야 한다. 

그래서 결론적으로는 DP 문제인데, 해결하려면 아래에서 한칸 아래인 n-1층에서 DP를 시작하면 되는데, 예를 들어 왼쪽 아래 
 2

4 5

는 2 = 2 + max(4, 5)처럼 위로 쌓아가면 된다. 그러면 2 7 4 4는 각각 아래 자식에서 큰걸 고르면 7 12 10 10 이 된다.
이처럼 아래에서 위로 max 값을 누적해가면서 쌓으면 O(n^2)으로 풀 수 있다.

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> triangle(n);

    for(int i=0; i<n; i++)
    {
        triangle[i].resize(i+1);
        for(int j=0; j<=i; j++)
        {
            cin >> triangle[i][j];
        }
    }

    for(int i = n-2; i>=0; i--)
    {
        for(int j=0; j<=i; j++)
        {
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }

    cout << triangle[0][0] << '\n';

    return 0;
}