https://www.acmicpc.net/problem/11055
문제
> 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
> 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에
합이 가장 큰 증가하는 부분 수열은 A = {1, 2, 50, 60} 이고, 합은 113이다.접근
dp를 사용하는데 여기서 dp(i)는 수열의 i번째 수 까지의 증가하는 부분수열의 최대값 이다.
즉 문제를 예시로 하면 dp(1)은 1까지 하는 최대값인 1이고
dp(2)는 100까지로 하는 수열인 1과 1,100과 100 중에 최대인 값을 나타낸다.
증가하는 부분 수열이므로 dp값을 구하기 위해선 i번째와 i번째 이전에 있는 수열의 수들과 전부 비교해 더 작은 애들만 따져준다.
이제 더 작은 애들만 골라냈으면(예를들어 dp(1), dp(3)이 골라졌다고 하면)그 dp(i)갑과 dp(1)+i값, dp(3)+i값 중 더 큰값을 고르면 된다.
따라서 i가 5인 60을 보면 i가 2인 100 빼곤 다 작으므로 dp(1), dp(3), dp(4)와 따져준다.
그래서 dp(6)과 dp(1)+num(6), dp(3)+num(6), dp(4)+num(6)중 가장 큰 값을 찾는다.
문제해결
> 수열의 합을저장할 dp벡터와 수열을 저장할 num벡터를 만든다.
> 1번인덱스부터 사용할것이므로 1부터 N까지 수열을 입력받고 동시에 dp값도 num(i)값인 자기자신으로 초기화 해준다.
> 각 i번째 수에 대해 i보다 전에 있는 j들과 모두 비교하며 더 작은 j들만 골라내어 max연산을 통해 최대 증가수열을 저장한다.
> 각 i에 대해 연산이 끝날 때마다 rst에 지금 까지의 i들중 누가 젤 큰 수열의 합을 가지는지 갱신 해준다.
> rst를 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<int> dp;
vector<int> num;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
dp.assign(N + 1, 0);
num.assign(N+1, 0);
for (int i = 1; i <= N; i++)
{
cin >> num[i];
dp[i] = num[i];
}
int rst = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j < i; j++)
{
if (num[i] <= num[j]) continue;
dp[i] = max(dp[i], dp[j] + num[i]);
}
rst = max(rst, dp[i]);
}
cout << rst << '\n';
}
후기
처음에 dp값을 전부 1로 초기화 해서 틀렸다.
뭐가 문제인가 생각해봤더니 각 dp는 i번째 수에 대해서 i번째 수 까지의 수열의 합의최대값을 말하는데 num(i)와 비교로 갱신이 되지 않으면 그냥 그 수에대한 수열은 1이 되는거라 논리 오류가 존재한다.
다음은 비교범위의 문제다. num(i) < num(j)에 대해 continue;로 했는데 여기서 문제는 num(j)와 num(i)가 같을 경우이다. 증가하는 수열이므로 같은 경우도 제해줘야 하므로 문제가 생긴다.
