문제

문제 링크

해설

• [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;
}

소스코드 링크

결과