[C++] BOJ 1932번: 정수 삼각형

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 실버 1로, dp 방식을 활용해 푸는 것을 권장받은 문제이다.

문제 링크

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

문제 분석

 이번 문제는 주어진 삼각형에 대하여, 모든 숫자의 합이 최대가 되는 경로에 있는 숫자의 합을 출력하는 문제이다.

자료 구조 및 알고리즘

DP (Dynamic Programming)

dp는 큰 문제를 작은 문제로 쪼개고 합쳐 문제를 해결하는 방식 중 하나이다. 중복되는 연산을 방지할 때 주로 사용되며, 이는 메모이제이션이라고도 한다. 예를 들어 피보나치 수열을 계산할 때에 DP를 사용할 수 있다.

문제 풀이

 이번 문제를 풀 때에 유심히 봐야할 것은 경로를 선택할 때에 현재 층에서 아래층에 있는 수를 고를 때, 대각선 왼쪽이나 대각선 오른쪽에 있는 것만을 선택할 수 있다는 점이다.

 

 경로에 대한 최댓값 식은 다음 식으로 작성할 수 있다. 아래층 c까지의 경로의 최댓값 = max(오른쪽 경로 a까지의 최댓값, 왼쪽 경로 b까지의 최댓값) + 현재 층의 값

 

 위의 식을 활용하면서 문제를 해결하도록 코드로 옮기면 아래와 같다.

전체 코드

#include <iostream>

using namespace std;

int triangle[501][501];
int dp[501][501];
int n;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

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

    dp[0][0] = triangle[0][0];

    int maxValue = dp[0][0];

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

    cout << maxValue << '\n';

    return 0;
}