[BOJ 1932] (DP) 정수 삼각형 (C++)

정수 삼각형 (Silver 1)

문제

전체 문제 보기

1932번: 정수 삼각형

접근법

삼각형에서 임의의 위치 (i, j) (i: 열, j: 행)의 수를 a(i, j)라 하고, 삼각형의 꼭짓점에서 출발해서 임의의 위치 (i,j)까지 도달했을 때 경로의 최대합을 f(i, j)라고 했을 때 f(i, j)는 임의의 위치 (i,j)의 좌측 상단 (i-1, j-1)까지의 경로의 최대합과 우측 상단(i-1, j)까지 경로의 최대합에 (i, j)의 수 a(i, j) 값을 더한 값이다. 점화식으로 표현하면 다음과 같다.

\[f(i, j) = \mbox{max}(f(i-1, j), f(i-1, j-1)) + a(i, j)\]

점화식대로 연산이 호출된다면 중복계산이 많아 시간복잡도는 \(O(2^n)\)으로 상당히 커진다. 동적 계획법을 활용하여 계산량을 줄여야 하는 문제이다.

구현

아래의 방식으로 구현하였다.

• 반복문을 활용한 bottom-up 방식으로 구현하였다.
• 한 번 계산한 결과를 cache 배열에 저장하여 재사용하였다.
• f(1,1)에서 f(n,n) 까지 값을 구한 후 f(n,1) 에서 f(n,n) 중 최대 값을 탐색하여 출력하였다.

#include <iostream>
#include <array>
#include <algorithm>
#define endl '\n'

using namespace std;

const int MAX = 501;
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int n; //1 <= n <= 500
    array<array<int, MAX>, MAX> cache{};

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            int input;
            cin >> input;

            cache[i][j] = max(cache[i - 1][j], cache[i - 1][j - 1]) + input;
        }
    }

    int maxNum = 0;

    for (int i = 1; i <= n; ++i)
    {
        maxNum = max(cache[n][i], maxNum);
    }
    cout << maxNum;

    return 0;
}

성능 평가

점화식에 따르면 시간 복잡도는 \(O(2^n)\)이지만, 동적 계획법을 활용하여 한변의 길이가 \(n\)인 삼각형의 모든 위치의 값을 계산하는 \(O(n^2)\)까지 최적화하였다. 공간 복잡도 또한 모든 위치의 계산 값을 저장해 야하기 때문에 \(O(n^2)\)이다.