오늘의 알고리즘

[C++] 백준 1932 정수 삼각형

하늘하늘 . 2022. 10. 7. 21:45
#include <iostream>
#include <vector>
#include <string>
 
int vec[501][501] = {};
int DP[501][501] = {};
 
int main()
{
    int N = 0;
    std::cin >> N;
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            int iNumber = 0;
            std::cin >> iNumber;
 
            vec[i][j] = iNumber;
        }
    }
 
    for (int i = 0; i < N; ++i)
    {
        DP[N - 1][i] = vec[N - 1][i];
    }
 
    for (int i = N - 2; i >= 0; --i)
    {
        for (int j = 0; j <= i; ++j)
        {
            DP[i][j] = std::max(vec[i][j] + DP[i + 1][j], vec[i][j] + DP[i + 1][j + 1]);
        }
    }
 
    std::cout << DP[0][0];
 
    return 0;
}

DP문제입니다.

아래서 부터 계산하면서 올라오는 게 중요합니다.

위에서 아래로 계산하는 것도 좋지만 아예 아래에서 위로 올라오면 한점으로 돌아오기 때문에 계산하기 쉽습니다.