글 읽기 - LIS - NlogN, 어느 부분이 잘못되었는지 잘 모르겠습니다. ㅠ

dudgus0627 5년 전 0

LIS를 NloN으로 구현하고 있습니다.

테스트를 하는데 계속 틀리네요

어느부분이 잘못되었는지 도움 요청드려요, 반례도 감사합니다.

#include <stdio.h>

#define MAX_N 100000
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int input[MAX_N];
int dp[MAX_N];
int c[MAX_N];

int binarySearch (int * arr, int target, int left, int right) {
    int middle;

    while (left <= right) {
        middle = (left + right) / 2;
        if (arr[middle] == target) return middle;
        else if (arr[middle] > target) right = middle - 1;
        else left = middle + 1;
    }

    return middle;
}

int main (void) {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
        scanf ("%d", &input[i]);
    
    int sz = 1;
    c[1] = input[0];
    dp[0] = 1;
    for (int i = 1; i < N; i++) {
        if (input[i] < c[1]) {
            c[1] = input[i];
            dp[i] = 1;
        } else if (input[i] > c[sz]) {
            c[sz+1] = input[i];
            dp[i] = sz+1;
            sz++;
        } else {
            int k = binarySearch(c, input[i], 0, sz);
            c[k] = input[i];
            dp[i] = k;
        }
    }

    int ret = 0;
    for (int i = 0; i < N; i++)
        ret = MAX(ret, dp[i]);

    printf ("%d\n", N - ret);

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

LIS - NlogN, 어느 부분이 잘못되었는지 잘 모르겠습니다. ㅠ

dudgus0627 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말