백준 11055
이 문제는 n개의 수열이 주어졌을 때, 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 문제이다.
dp[i]는 i번째 인덱스를 포함하고, i번째 숫자가 가장 큰 증가 부분 수열의 최대합이다. 0부터 i보다 작은 인덱스까지 숫자를 비교해서 arr[i]>arr[j] 이면 dp[i]=max(dp[i],dp[j]+arr[i]) 로 식을 세운다. dp[j]+arr[i]는 j번째 인덱스까지의 최대합이고 i번째 수를 더해서 비교하는 것이다.
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[1001]; int dp[1001];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
dp[i] = arr[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) // 증가 부분 수열이 되는지 확인
dp[i] = max(dp[i], dp[j] + arr[i]);
}
}
sort(dp, dp + n);
cout << dp[n - 1] << '\n';
}
비슷한 문제 백준 11053
Author And Source
이 문제에 관하여(백준 11055), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@supway/백준-11055저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)