글 읽기 - 줄세우기 문제 lower_bound로는 해결못하나요?

kkw564 7년 전 2

이걸로는 왜 해결이 안되는거죠??

같은 맥락으로 가장 긴 증가하는 부분 수열의 수를 찾고 n - 결과를하는것인데

왜 틀린걸까요..?

#include <iostream>
#include <cstdio>

using namespace std;

int arr[1000001];
int lis[1000001];

int _lower_bound(int start, int end, int target)
{
    int mid;

    while(start < end)
    {
        mid = (start+end)/2;

        if(lis[mid] < target)
            start = mid + 1;

        else
            end = mid;
    }

    return end + 1;
}

int main()
{
    int n;

    scanf("%d",&n);

    for(int i = 0; i < n ; i ++)
        scanf("%d",&arr[i]);

    int pLis = 0, pArr = 1;
    int cnt = 0;

    lis[pLis] = arr[0];

    while(pArr < n)
    {
        if(lis[pLis] < arr[pArr])
            lis[++pLis] = arr[pArr];

        else
        {
            int ans = _lower_bound(0, pLis, arr[pArr]);
            lis[ans-1] = arr[pArr];
        }

        pArr++;
    }

    printf("%d",n - (pLis + 1));

    return 0;
}

portableangel 7년 전 1

2,3,5가 순서대로 서있을 때, 4번이 2,3,5를 건드리지 않고 안에 들어갈 방법이 있을까요?
맨 앞이나 뒤로만 보낼 수 있다는 조건을 잘 생각해보시면, 옮겨지지 않은 아이들의 번호는 증가할 뿐 아니라 연속해야 한다는 사실을 알 수가 있습니다.

kkw564 7년 전 1

2 3 5를 입력시 제 코드는 답이 0이 나옵니다. 이문제의 핵심이 가장 긴 부분 증가 수열이어야 하는것으로 알고있습니다

portableangel 7년 전 17

예를 들어, 1 2 3 5 6 4 와 같은 배치에서, 한 명의 학생을 움직이는 것으로는 증가순으로 배치할 방법이 없습니다.

4번 학생이 가운데로 들어갈 수 없기 때문입니다. 답은 2명입니다. (5,6이 뒤로 옮겨짐)

실제로 학생을 옮겨 보시면 맨 앞/ 맨 뒤로 보내는 연산 2회 미만으로는 1 2 3 4 5 6을 만들 수 없다는 것을 보실 수가 있습니다.

말씀하신 LIS 풀이는 학생이 임의의 위치로 끼어들어갈 수 있는 문제에서의 풀이입니다.

움직인 학생을 최소화 = 움직이지 않은 학생을 최대화 -> 움직이지 않은 학생들은 증가 순이어야 함

으로부터 나온 풀이이고, 이 문제와는 다릅니다.

이 문제에도 똑같이 적용해보면,

움직인 학생을 최소화 = 움직이지 않은 학생을 최대화 -> 움직이지 않은 학생들은 증가 순이어야 하며, 번호가 서로 붙어있어야 함

으로 진행이 가능합니다.

kkw564 7년 전 1

감사합니다 이해하는데 도움이 됐네요 ㅎ

nosun4938 1년 전 0

5년전의 선배님들 감사합니다 같은 실수를 하고 있었네요

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

문제

문제

출처

ICPC

줄세우기 문제 lower_bound로는 해결못하나요?

kkw564 7년 전 2

portableangel 7년 전 1

kkw564 7년 전 1

portableangel 7년 전 17

kkw564 7년 전 1

nosun4938 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말