백준 11055번 가장 큰 증가 부분 수열 (C++)

문제 링크 : www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

이 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장판 문제이다.

 

이 문제에서는 유의 사항이 하나 있다. 

정답이 될 수 있는 조건의 우선 순위가 아래와 같다는 점이다.

1. 수열의 합이 크고

2. 수열은 증가하는 수열이어야 한다.

 

즉, 증가 길이가 무조건 길다고 정답이 아니라

증가하는 수열이면서 동시에 그 합이 커야지 정답이 될 수 있다.

이 점을 간과했다고 채점과 동시에 바로 틀려버리고 말았다.

 

문제 풀이는 다음과 같다.

 1. 배열 arr[1] ~ arr[n]까지 입력 받는다. 이때 누적합을 입력받을 dp[1] ~ dp[n] = arr[1] ~ arr[n]으로 동일하게 저장해준다.

2. 정답변수 ans의 초기값은 dp[1]로 저장해준다.

3. 배열의 i=2번째 값부터 for문을 시작해준다. 

4. 이중 for문으로 j=1; j<i로 설정해준다.

5.  arr[i] > arr[j]의 조건을 만족하면서 = 증가하는 수열

동시에 dp[i] < dp[j] + arr[i]의 조건을 만족하면 = 누적합이 크다

dp[i] = dp[j] + arr[i]가 된다. 또한 이 값이 정답 변수 ans보다 크면 ans에 그 값을 저장해준다.

 

#include <iostream>
#define MAX 1001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, len = 1, ans = 0, arr[MAX] = {0,}, dp[MAX] = {0,};
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        dp[i] = arr[i];
    }
    ans = dp[1];
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(arr[i]>arr[j]&&dp[i]<dp[j]+arr[i]){
                dp[i] = dp[j] + arr[i];
                if(dp[i]>ans) ans = dp[i];
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

처참한 뻘짓의 흔적들