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

BOJ : https://www.acmicpc.net/problem/11055

GitHub : https://github.com/junho0956/Algorithm/blob/master/11055/11055/%EC%86%8C%EC%8A%A4.cpp

 

꼼꼼하지못하면 사람이 고생을 하는 것 같다.

저번 포스팅때 꼼꼼해지자 해놓고 또 덜렁대다 WA를 받은 문제이다.

 

다른분들은 어떤방식으로 풀었는지 참고해봐야 될 것 같다

 

생각해볼만한 요소는 이정도 인것 같다.

부분수열의 길이를 찾는 것이 아닌 부분수열의 합 중 가장 큰 값을 찾는 것이니,

DP를 이런식으로 구현해보았다.

현재 숫자로 가질 수 있는 최대값과 이때 현재 숫자를 동시에 저장해서 증가하는 부분수열을 찾아 값을 갱신시키자

(그래서 코드를 보면 2*1000으로 해놨는데

결국에는 현재 숫자를 동시에 저장한다는 것은 arr 배열을 참조했어도 된다.)

 

1 100 2 50 60 3 5 6 7 8 을 예로 들면

2중반복문을 이용해서 현재 비교할 값의 인덱스를 그 전인덱스까지 모두 비교해주면서

현재값보다 작은 값(arr)을 발견하면 그 인덱스의 DP 값과 비교하여 값을 채워나갔다.

* 전 인덱스까지 다 확인후에는 현재 값보다 작은 값이 없을 수도 있으므로

DP에는 현재값을 넣어주는 작업을 반드시 해야한다*

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001];
int dp[2][1001];
int N, Max, idx;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
    
    dp[0][0] = dp[1][0] = arr[0];
    Max = dp[0][0];
    for (int i = 1; i < N; i++) {
        bool check = false;
        for (int k = 0; k < i; k++) {
            if (arr[i] > dp[1][k] && dp[0][k]+arr[i] > dp[0][i]) {
                dp[0][i] = dp[0][k] + arr[i];
                dp[1][i] = arr[i];
                check = true;
            }
            Max = max(Max, dp[0][i]);
        }
        if (!check) dp[0][i] = dp[1][i] = arr[i];
    }
 
    cout << Max;
    return 0;
}

복습 20.02.09