백준 14003 번 : 가장 긴 증가하는 부분 수열 5

문제

문제 분석

증가 수열 문제 시리즈를 몇개 풀어봐서 얕봤었다.... 어려웠다. 다른 점이라곤 범위가 0에서 -10만정도로 바뀐 것이고 경로를 추가로 출력해야 했었다.

가장 먼저 생각난 것은 갯수를 구할때 쓰인 DP를 그대로 이용하는 것이었다. DP[i]는 길이가 i인 증가하는 수열에서 가장 작은 끝값을 저장하는 것이었는데 이 모양이 부분 증가수열이라서 그대로 이것을 출력했는데 틀렸었다.

당연한게 이것은 가장 긴 증가하는 부분 수열을 위해서 계속 갱신되기 때문이다. 예를 들어 456712이런 수열이 존재한다면 DP에는 4567이 아닌 1267이 존재할 것이고 이는 입력의 증가하는 부분 수열이 아니므로 틀리게 되는 것이다.

그래서 이 경로를 저장할 두번째 방식으로 생각해낸 것이 각 인덱스 별로 (부분수열별로) path를 갖고, 하나 추가되면 이전 경로를 복사하고,  새 값을 붙여서 i+1의 경로로 저장하고, 갱신된다면 i번째의 path에서 끝값을 바꾸는 방식으로 구현하고자 하였다.

하지만 n = 1,000,000이고 1 + 2 + 3...+n = n^2이므로 30여 퍼센트 이후로 메모리 초과가 났었다.

반드시 1차원 배열로 경로를 표현해야 한다는 것을 알고, 생각을 전환해야했다. i번째 입력을 처리할 때, j번째 위치에 값이 배정되었다면(즉, 갱신되거나 새로 추가되었다면) ARR[i] = j를 해주었다. 그리고 마지막에 N부터 1까지 내려가면서  최종 수열의 길이, len(path)부터 1까지 차례대로 가장 최근에 존재한 인덱스를 찾으면 된다. 왜냐하면 현재 찾고자 하는 것이 k번째 원소라고 할 때 가장 마지막에 나온 k값을 갖는 것이 path의 구성 원소이고 그 이전의 것은 모두 무시되어야 할 것들이기 때문이다. (그 사이에 나온 1~k-1은 갱신을 위해 사용된 것이므로, path에 속할 수 있는 k-1번째 원소는 반드시 k를 찾은 후에 나와야 한다. )

 

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함


using namespace std;

typedef long long int lld;
// 2차원 DP? : 10^6 -> 12ㄴㄴ
// 1+2+3....+10^6 -> 10^12 (대충), 1억 = 10^8 ㄴㄴ 
vector<int> DP;
vector<int> input_v;
int p[1000001] = {0};

int binary_search(int n)
{
    int hi = DP.size()-1;
    int low = 1;
    int mid = 0;
    while(hi > low)
    {
        mid = (hi+low)/2;
        if(n > DP[mid])
            low = mid+1;
        else if (n < DP[mid])
            hi = mid;
        else
            return mid;
    }
    // cout << low << " " << mid << " " << hi << endl;
    return hi;
}

void solution()
{
    // code
    int N;
    cin >> N;
    vector<int> tmp_v;
    for(int i=0; i<N; i++)
    {
        int tmp_int;
        cin >> tmp_int;
        input_v.push_back(tmp_int);
    }
    DP.push_back(-1000000001);
    for(int i=0; i<input_v.size(); i++)
    {
        if(DP[DP.size()-1] < input_v[i])
        {
            DP.push_back(input_v[i]);
            tmp_v.push_back(input_v[i]);
            p[i] = DP.size()-1;
        }
        else
        {
            int cmp_idx = binary_search(input_v[i]); 
            DP[cmp_idx] = input_v[i];
            p[i] = cmp_idx;
        }
    }
    vector<int> output;
    int now_val = DP.size()-1;
    for(int i = N-1; i>=0; i--)
    {
        if(p[i] == now_val)
        {
            output.push_back(input_v[i]);
            now_val--;
        }
        if(now_val == 0)
            break;
    }
    cout << DP.size()-1 << endl;
    for(int i=output.size()-1; i>=0; i--)
    {
        cout << output[i] << " ";
    }


}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

메모리와 실행 시간을 항상 염두해두자.