간단한 dp 문제이다. 삼각형 값의 최댓값을 구하는 것이 목적이므로 현재 위치에서의 최댓값을 구해 더해나가야 한다. 현재 위치에서의 최댓값은 현재 위치까지의 합, 왼쪽 위 대각선 값 + 현재 위치 값, 오른쪽 위 대각선 값 + 현재 위치 값 중 하나이다. 이를 dp를 사용해 점화식으로 표현하면 다음과 같다.
dp[i][j] = max({ dp[i][j], dp[i - 1][j - 1] + v[i][j], dp[i - 1][j] + v[i][j] })
대각선 값이 하나일 경우인 가장 첫번째 값과 마지막 값은 조건문으로 분류하여 처리하였다. 간단하게 풀 수 있었던 문제였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, res = 0;
vector<int> v[500];
int dp[500][500];
void solution() {
dp[0][0] = v[0][0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j] + v[i][j]);
}
else if (j == i) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + v[i][j]);
}
else {
dp[i][j] = max({ dp[i][j], dp[i - 1][j - 1] + v[i][j], dp[i - 1][j] + v[i][j] });
}
}
}
for (int i = 0; i < n; i++) {
res = max(res, dp[n - 1][i]);
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
int a;
cin >> a;
v[i].push_back(a);
}
}
solution();
return 0;
}