14003_가장 긴 증가하는 부분 수열5

Concept & Idea

앞서 공부했던 LIS 알고리즘을 이용하여 문제를 해결할 수 있었다.
map은 입력받는 배열이고, p1은 수열을 출력하기 위한 순서를 기록해놓는 배열이다. 또한 LIS 알고리즘을 이용하려면 LIS를 체크하기 위한? 배열이 있어야한다. 내 코드에선 그 배열이 T배열이다.

int lowIndex = lower_bound(t+1, t+pIndex, map[i])-t;

이 코드에서 틀렸습니다를 고칠 수 있었다. 나는 배열의 시작을 0부터 하지 않고 1부터 했으며, 이 문제의 입력으로 음수가 들어올 수 있다.
그래서 0과 음수를 비교했을 때, lower_bound에서 오류가 나왔기 때문에 오답을 냈다. 배열의 시작주소를 +1하니 문제를 해결할 수 있었다.
이 문제에서 또 핵심적인 하나의 아이디어는 pIndex를 기록하고 순서를 기록했던 배열에 거꾸로 접근하면서 스택에 푸쉬하여 수열을 가져오는 것이었다.

Code

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n;
int map[1000002];
int p1[1000002];
int t[1000002];
stack<int> st;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d",&map[i]);
    t[1]=map[1];
    p1[1]=1;
    int pIndex=1;
    for(int i=2; i<=n; i++) {
        if(map[i]>t[pIndex]) {
            pIndex++;
            p1[i]=pIndex;
            t[pIndex]=map[i];
        } else {
            int lowIndex = lower_bound(t+1, t+pIndex,  map[i])-t;
            p1[i]=lowIndex;
            t[lowIndex]=map[i];
        }
    }
    int len = pIndex;
    for(int i=n; i>=1; i--){
        if(p1[i]==len) {
            st.push(map[i]);
            len--;
        }
    }
    cout<<pIndex<<endl;
    while (!st.empty()) {
        printf("%d ",st.top());
        st.pop();
    }
    cout<<endl;
}

 

Fealing

후우.. 하루종일 고생했다..
입력값이 음수가 들어올 수 있음을 알았는데도, 내 코드와 상관없는 이야기라고 생각했는데 아니었다.
다른 다이나믹 프로그래밍 문제를 풀 때는, 배열 시작을 1부터 했는데 입력이 음수부터 가능하다면 dp[0]이 0으로 초기화되어있기 때문에 틀릴 수 밖에 없다.