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

  휴... 어떻게 얼기설기 풀었다. 어려운 문제일수록 뭔가 아름답게 푸는 방법이 있을 것이라는 생각이 드는데 음... 나는 사실 문제를 푸는게 우선이라서 아름다운 코드를 생각할 단계가 아니라는 생각이 든다.

  아무튼 이 문제는 11053번 문제의 심화버전이다. 11053번이 단순히 길이만을 출력하는 문제라면 이 문제는 그 수열 자체를 출력해야 하는데 각 항이랑 연결된 위치를 나타내는 con이라는 수열을 추가했다. (con은 connect의 약자다)

 

문제의 예시를 내 코드에 적용시켜보면 그림과 같다.

  len이 제일 긴 녀석을 미리 저장해둔 뒤 len이 제일 긴 (예시에서는 index = 5가 제일 길기 때문에) 50에서 con을 따라 역행한다.

• con = 3이므로 index = 3인 30으로 가고
• 30의 con = 1이므로 index = 1인 20으로 간다.
• 20의 con = 0이므로 index = 0인 10으로 간다.
• 마지막으로 10의 con = -1이므로 갈 수 있는 곳이 없으므로 끝낸다.

 

  근데 문제는 이게 역행이다보니 바로 출력하면 안된다. 그래서 이걸 출력하기 전에 어떤 vector에 적용시켜뒀다가 algorithm을 이용해 sorting을 하거나 나는 뭔가 sorting을 쓰면 O(log n)만큼의 시간이 더 걸릴 것 같아서 각각의 index를 저장해 놓은 뒤 for문을 이용해 뒤에서부터 출력했다. (애초에 역순으로 저장이 되어있으므로 뒤에서부터 출력하면 정순이다.)

 

#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;

int n;
int seq[1004];
int len[1004];
int con[1004];
int maxLen, maxIndex;

int main()
{
    cin >> n;
    
    for(int i = 0; i <= n; i++)
    {
        cin >> seq[i];
    }
    
    len[0] = 1;
    con[0] = -1;
    maxLen = 1;
    maxIndex = 0;
    
    for(int i = 1; i < n; i++)
    {
        len[i] = 1;
        con[i] = -1;
        for(int j = 0; j < i; j++)
        {
            if(seq[j] >= seq[i]) continue;
            if(len[i] > len[j] + 1) continue;
            
            len[i] = len[j] + 1;
            con[i] = j;
        }
        if(len[i] > maxLen)
        {
            maxLen = len[i];
            maxIndex = i;
        }
    }
    
    vector<int> ansIndex;
    ansIndex.push_back(maxIndex);
    
    int target = maxIndex;
    while(con[target] != -1)
    {
        ansIndex.push_back(con[target]);
        target = con[target];
    }
    
    int size = ansIndex.size();
    cout << size << "\n";
    
    for(int i = 1; i <= size; i++)
    {
        cout << seq[ansIndex[size - i]] << " ";
    }
 
    return 0;
}