▶실버2
풀이
기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다.
위의 예제를 표로 나타내면
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 1 + 2 = 3 | max(1, 3) + 50 = 53 | max(1, 3, 53) + 60 = 113 | max(1, 3) + 3 = 6 | max(1, 3, 6) + 5 = 11 | max(1, 3, 6, 11) + 6 = 17 | max(1, 3, 6, 11, 17) + 7 = 24 | max(1, 3, 6, 11, 17, 24) + 8 = 32 |
dp값 중 가장 큰 값이 답
코드
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[1001];
int arr[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
dp[i] = arr[i];
}
for (int i = 0; i < n; i++) {
if (i == 0) {
ans = dp[i];
}
for (int j = 0; j < i; j++) {
//증가 수열 조건 만족
if (arr[j] < arr[i]) {
dp[i] = max(dp[j] + arr[i], dp[i]);
}
//증가 수열 조건 불만족
else continue;
}
ans = max(ans, dp[i]);
}
cout << ans;
}
'Algorithm > Baekjoon' 카테고리의 다른 글
1699_제곱수의 합 (0) | 2023.01.13 |
---|---|
11660_구간 합 구하기 5 (0) | 2023.01.11 |
11057_오르막수 (0) | 2023.01.04 |
2003_수들의 합 2 (0) | 2023.01.02 |
21921_블로그 (0) | 2023.01.01 |