[PS] 백준 15966번 - 군계일학

LIS와 유사한 문제, 다양한 방법으로 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int a[100001], exist[1000001], N;

int binary_search(int start, int end, int element) {
    while (start < end) {
        int mid = (start + end) / 2;
        if (element > a[mid]) start = mid + 1;
        else end = mid;
    }
    if(a[end]==element) return end;
    else return -1;
}

int main(void) {
    cin >> N;
    for(int i=0; i<N; i++) cin >> a[i];
    sort(a, a+N);
    for(int i=1; i<=1000000; i++) {
        if(binary_search(0, N, i)==-1) exist[i]=0;
        else exist[i]=1;
    }
    int max=1, cnt=1;
    for(int i=1; i<1000000; i++) {
        if(exist[i] && exist[i+1]) cnt++;
        else cnt=1;
        if(cnt>max) max=cnt;
    }
    cout << max;
    return 0;
}

먼저 위 코드와 같이 Binary Search를 활용하여 풀 수도 있는데 왜 인지 몰라도 50%에서 계속 짤리는 일이 일어났다.

 

i에서 끝나는 군계일학 수열의 최대길이를 a[i]라 하여 DP를 활용하면 다음과 같이 정풀을 띄울 수 있다.

#include <iostream>

using namespace std;

int a[100000]={}, l[1000001]={}, N;

int main(void) {
    cin >> N;
    for(int i=0; i<N; i++) cin >> a[i];
    int ans=0;
    for(int i=0; i<N; i++) {
        l[a[i]]=max(l[a[i]-1]+1, l[a[i]]);
        ans=max(l[a[i]], ans);
    }
    cout << ans;
    return 0;
}