오늘의 알고리즘
[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문제입니다.
아래서 부터 계산하면서 올라오는 게 중요합니다.
위에서 아래로 계산하는 것도 좋지만 아예 아래에서 위로 올라오면 한점으로 돌아오기 때문에 계산하기 쉽습니다.