# 문제
# 입력 및 출력
# 풀이
dp[n] = max(dp[0]+dp[n], dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n-1]+dp[1])
중복되는 값은 있지만 간단한 반복문으로 구현하기 위해 그냥 위의 식으로 풀었음
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> dp[i];
}
for (int i = 1; i <= n; i++) {
int maxv = dp[i];
for (int j = 1; j < i; j++) {
maxv = max(maxv, dp[j] + dp[i - j]);
}
dp[i] = maxv;
}
cout << dp[n];
}
'Algorithm > 📖Baekjoon' 카테고리의 다른 글
#2193 이친수 (0) | 2022.06.29 |
---|---|
#1966 프린터 큐 (0) | 2022.06.28 |
#11403 경로 찾기 (0) | 2022.06.25 |
#1004 어린 왕자 (0) | 2022.06.24 |
#1051 숫자 정사각형 (0) | 2022.06.23 |
댓글