문제
문제 링크
해설
[y][x]
는 [y + 1][x]
와 [y + 1][x + 1]
두 요소로 타고 내려갈 수 있습니다.
- 1층은 원소가 하나밖에 없기 때문에 항상 최댓값을 가집니다.
- 2층부터는 위 두 요소 중 더 큰 값으로 최댓값으로 초기화하면서 한 층씩 내려가면 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
vector<vector<int>> A(N), DP(N);
for (int n, i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
cin >> n;
A[i].push_back(n);
DP[i].push_back(0);
}
}
DP[0][0] = A[0][0];
for (int y = 0; y < N - 1; ++y) {
for (int x = 0; x <= y; ++x) {
DP[y + 1][x] = max(DP[y + 1][x], DP[y][x] + A[y + 1][x]);
DP[y + 1][x + 1] = max(DP[y + 1][x + 1], DP[y][x] + A[y + 1][x + 1]);
}
}
int ans = 0;
for (int x = 0; x < N; ++x) ans = max(ans, DP[N - 1][x]);
cout << ans;
}
소스코드 링크
결과