[백준] 11055번 : 가장 큰 증가 부분 수열

문제

 

---

풀이

 

내가 원래 LIS를 풀던 방식으로 풀려다가 엄청난 삽질을 했다.

 

myunji.tistory.com/214

[백준] 11053번 : 가장 긴 증가하는 부분 수열

이게 내가 원래 LIS를 풀던 방식...

 

이 문제에선 dp에 최장 길이를 저장할 필요가 없다. 우리가 찾는건 가장 큰 수열의 합이기 때문이다.

그래서 O(n^2)의 시간복잡도로 진행을 할 것이다. 말로 설명하면 어려우니 데이터로 설명하겠다.

 

1 100 2 50 20 60 3 5

의 데이터가 있다고 하자.

 

0	1	100	2	50	20	60	3	5
0	1

길이가 1인 경우(최솟값)에 대비하여 맨 앞에 0을 넣어놨다.

arr[index]에 대해 0부터 index-1까지의 수를 arr[index]와 비교한다.

특정 arr[k]에 대해 이 수보다 arr[index]가 더 크다면 이 둘은 증가 관계일 것이다.

그리고 나서 dp[index]와 dp[k]를 비교한다. dp[k]+arr[index]가 dp[index]보다 크다면 dp[index]를 갱신하는 것이다.

 

저 표를 기준으로 계속 해보도록 하겠다.

0	1	100	2	50	20	60	3	5
0	1	100

arr[0]<arr[2] 이면서 dp[0]+arr[2]>dp[2] 이기 때문에 dp[2]는 100으로 갱신된다.

 

0	1	100	2	50	20	60	3	5
0	1	101

하지만 역시 arr[1]<arr[2] 이면서 dp[1]+arr[2]>dp[1] 이기 때문에 dp[2]는 다시 101로 갱신된다.

 

여기서 좀 더 해보면

0	1	100	2	50	20	60	3	5
0	1	101	3	53	23	113

이런 상황이 된다.

현 상황은 arr[6]인 60에 대해 dp[6]을 구하는 과정이고 i=4까지의 비교를 마쳐 dp[6]이 113으로 갱신된 상황이다.

 

i=5가 되었고, arr[5]<arr[6] 이라서 둘은 증가 관계이다.

하지만 dp[5]+arr[6] = 83이고 dp[6] = 113, 즉 dp[5]+arr[6]<dp[6]이기 때문에 dp[6]을 갱신하지 않는다.

 

0	1	100	2	50	20	60	3	5
0	1	101	3	53	23	113	6	11

최종 결과는 이렇게 될 것이고 dp[i]중 가장 큰 값인 113을 반환하면 되겠다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1001], dp[1001];

int lis(int n) {
    int result = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) //증가 수열 관계라면
                dp[i] = max(dp[i], dp[j] + arr[i]); //해당 인덱스의 최대 합과 비교하여 갱신
        }
        result = max(result, dp[i]); //최대 합 갱신
    }
    return result;
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    cout << lis(N) << '\n'; //최대 합 출력
}