발상
지금까지의 문제들은 모두 일차원 선상의 문제였지만 ‘평면상에서’ 뭔가를 하는 문제가 나왔다. 하지만 이전에 인자를 설정하던 것을 기억한다면 그냥 똑같은 문제라는 걸 알 수 있다. 선상에서 평면상이 되었다는 것은 축 위치가 하나 더 추가되었다는 뜻이다. 즉, 인자가 하나 추가 된 것 뿐이다!
기저 사례가 자명하므로 거기서부터 출발해보자. 당연히 출발점이 기저사례가 된다.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
이 예시에서는 1행의 7이 기저사례가 된다. 이 후, 다른 위치에서의 최적값은 자기 위에 있는 두 부모의 최적값 중 큰 것을 현재 위치값에 더한 값이 된다. 단, 외곽은 부모가 하나밖에 없으므로 그 부모의 최적값만 더하여 구한다. 각 행별로 다음과 같이 진행된다.
no1
7
0 0
0 0 0
0 0 0 0
0 0 0 0 0
no2
7
10 15
0 0 0
0 0 0 0
0 0 0 0 0
no3
7
10 15
18 16 15
0 0 0 0
0 0 0 0 0
no4
7
10 15
18 16 15
20 25 20 19
0 0 0 0 0
no4
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24
따라서 답은 30이다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n; vector<vector<int>> arr(n + 1), dp(n + 1);
for(int i=1;i<=n;i++) {
arr[i] = dp[i] = vector<int>(i + 2);
for(int j=1;j<=i;j++) {
cin >> arr[i][j];
}
}
dp[1][1] = arr[1][1];
for(int i=2;i<=n;i++) {
for(int j=1;j<=i;j++) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];
}
}
cout << *max_element(dp[n].begin(), dp[n].end());
return 0;
}2차원 이라는 점을 제외하면 이전 문제들과 특별하게 다른 점은 없다.