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

문제

 

---

풀이

 

myunji.tistory.com/214

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

단순히 수열의 길이만 구하던 위 문제에서 응용된 문제이다.

 

처음에는 그냥 length가 늘어날 때마다 dp 배열을 그대로 복사하면 되는거 아닌가? 했다가 반례를 만났다.

 

10 3 7 4 1 8

 

이 경우 11053에서 작성한 내 코드 기준 dp를 그대로 복사해오면 1 4 8이란 결과가 나온다.

딱봐도 말도 안된다는 것을 알 수 있다.

 

그래서 배열의 각 index마다의 최장 길이를 저장하기로 했다.

10	3	7	4	1	8
1	1	2	2	1	3

 

이런식으로 저장된다. 당연히 최장 길이인 3도 다른 변수에 저장해둔다.

그리고 배열의 가장 오른쪽인 8부터 10까지 돌면서 최장길이 3, 2, 1을 하나하나 찾아 스택에 넣는다.

8, 4, 3의 순서로 저장된다. 그리고 스택의 성질상 순서대로 출력하면 3, 4, 8이 출력된다.

---

소스코드

 

#include <iostream>
#include <stack>

using namespace std;

int arr[1001][2], dp[1001]; //arr[i][1] = k, i번째 원소의 최장 길이 수열의 길이는 k
stack<int> result;

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

    for (int i = 1; i <= n; i++) {
        for (int j = length; j >= 0; j--) {
            if (arr[i][0] > dp[j]) {
                dp[j + 1] = arr[i][0];
                arr[i][1] = j + 1; //i번째 원소의 길이 저장
                if (j == length) //최장 길이 증가
                    length++;
                break;
            }
        }
    }
    int tmp = length; //길이 임시 저장
    for (int i = n; i >= 1; i--) {
        if (arr[i][1] == tmp) { //인덱스 확인하며 스택에 투입
            result.push(arr[i][0]);
            tmp--;
        }
    }
    return length;
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i][0];
    cout << lis(N) << '\n'; //길이 출력
    while (!result.empty()) { //수열 출력
        cout << result.top() << ' ';
        result.pop();
    }
}

최장길이 index를 저장하기 위해 arr를 2차원 배열로 바꾸었고 스택에 데이터를 넣는 부분을 추가했다.