[C++] 백준 온라인 저지 1932번 정수 삼각형 풀이

정수로 이루어진 삼각형의 맨 위에서부터 특정 경로를 타고 밑으로 내려갈 때, 숫자의 합들이 최대가 되는 값을 구하는 문제

 

---

 

문제의 조건

 

 

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

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

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

 

입력

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

 

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

풀이 과정

 

 삼각형을 입력 받는 부분을 어째야 할 지 몰라서 쬐끔 헤멨던 문제. 삼각형의 위에서부터 밑으로 내려가면서 대각선 방향으로 더한 값 중 최대값을 DP 배열에 저장한 뒤 맨 마지막 줄 원소 중 가장 큰 값을 출력했습니다. 

 

1. 삼각형의 크기 n x n 크기로 DP 배열을 만든다. 

 

2. 삼각형의 두번째 줄 까지 기저조건으로 설정해 놓은 다음 반복문으로 i = 2부터 대각선 위에 있는 수와 현재 원소의 값을 더한 값을 DP 배열에 저장한다. 삼각형을 예제로 주어진 것처럼 배열에 저장하면 직각삼각형 모양이 된다. 그렇기 때문에 대각선 방향에 있는 수들의 합을 구하기 위한 점화식은 현재 삼각형의 i = 1번째 줄을 탐색하고 있다고 할 때 

DP[i][j] = DP[i-1][j] + triangle[i][j]

DP[i][j+1] = DP[i-1][j] + triangle[i][j+1] 이 된다. 

 

 그런데 이렇게 계산하다 보면 아래 그림처럼 중간에 겹치는 원소가 생긴다. 

 

 

 이 때 처음에 구했던 점화식을 그대로 쓰면 단순히 나중에 계산한 값으로 덮어쓰기가 되기 때문에 두 값을 비교해서 더 큰 값을 저장해야 한다. 그러면 다음과 같은 점화식을 수정할 수 있다. 

DP[i][j] = max(DP[i-1][j] + triangle[i][j], DP[i][j]);

DP[i][j+1] = max(DP[i-1][j] + triangle[i][j+1], DP[i][j+1]);

 반복문으로 이걸 반복하면서 끝까지 탐색 

 

3. DP 배열의 마지막 줄 원소 중 가장 큰 값을 출력한다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int triangleSize;
    cin >> triangleSize;
    
    vector<vector<int>> triangle(triangleSize);
    for (int i = 0; triangleSize > i; i++)
    {
        for (int j = 0; i + 1 > j; j++)
        {
            int a;
            cin >> a;
            triangle[i].emplace_back(a);
        }
    }
    
    unsigned answer = 0;
    vector<vector<unsigned>> DP(triangleSize, vector<unsigned>(triangleSize, 0));
    DP[0][0] = triangle[0][0]; //기저 조건
    if (1 == triangleSize) //사이즈가 1일 때 예외처리 
        answer = triangle[0][0];
    else
    {
        DP[1][0] = DP[0][0] + triangle[1][0];
        DP[1][1] = DP[0][0] + triangle[1][1];
        for (int i = 2; triangleSize > i; i++)
        {
            //j+1을 함께 구하니까 인덱스 에러 방지를 위해서 i번째 벡터 사이즈보다 2 작을 때까지 탐색 
            for (int j = 0; triangle[i].size() - 1 > j; j++)
            {
                DP[i][j] = max(DP[i-1][j] + triangle[i][j], DP[i][j]);
                DP[i][j+1] = max(DP[i-1][j] + triangle[i][j+1], DP[i][j+1]);
            }
        }
        answer = *max_element(DP.back().begin(), DP.back().end());
    }
    
    cout << answer;
    
    return 0;
}