백준 31816 (C++) Closet

최초 업로드: 2025-10-24 16:00:20

최근 수정 시간: 2025-10-24 16:03:11

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Closet

[문제 링크](https://www.acmicpc.net/problem/31816)

## 문제 설명

태인이의 옷장에는 $N$개의 옷이 일렬로 걸려 있다. 현재 왼쪽에서 $i$번째 옷의 색은 $c_i$이다.

태인이는 어떤 정수 $k$ ($1\le k\le N$)가 존재해 $c_1\leq c_2\leq\cdots\leq c_k\geq c_{k+1}\geq\cdots\geq c_N$를 만족하면 옷장이 아름답다고 생각한다.

하지만 옷장을 아름다운 상태로 정리하는 것은 꽤 귀찮다. 그래서 태인이는 옷장에서 최대 $M$개의 옷을 제거해 남은 옷들을 거의 아름다운 상태로 만들기로 했다.

최대 $M$개의 옷을 제거한 후, 남은 옷들의 개수를 $L$, 왼쪽에서 $j$번째 옷의 색을 $d_j$라 하자. 태인이는 인접한 두 옷의 색의 차가 $x$ 이하라면 두 옷을 같은 색으로 인식하기로 했다. 즉, 다음을 만족하는 정수 $k$ ($1\le k\le L$)가 존재한다면 옷장이 거의 아름다운 상태라고 한다.

$M$개 이하의 옷을 제거해 옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 음이 아닌 정수 $x$의 값을 구하자.

## 입력

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다.

두 번째 줄에 $N$개의 정수 $c_1,c_2,\ldots ,c_N$가 공백을 사이에 두고 주어진다.

## 출력

옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 $x$ ($x\ge 0$)의 값을 출력한다.

## 풀이
좌표압축 후 세그먼트 트리를 이용하여 LIS와 LDS를 구하여 몇 개의 점을 생략하고 만들 수 있는지 알 수 있다. 이를 파라메트릭 서치로 반복하여 가장 작은 x를 구하면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'001;

int n, m, _size=1, c[MAX], arr[MAX*4], increasingCnt[MAX], decreasingCnt[MAX];
vector<int> vals;

int search(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum];
 int mid = nodeL+nodeR>>1;
 return max(search(L, R, nodeNum*2, nodeL, mid), search(L, R, nodeNum*2+1, mid+1, nodeR));
}

void update(int idx, int val) {
    idx += _size/2;
    arr[idx] = max(arr[idx], val);
    while(idx>1) {
        idx>>=1;
        arr[idx] = max(arr[idx*2], arr[idx*2+1]);
    }
}

void construct(int x) {
 memset(arr, 0, sizeof arr);
 for(int i=0;i<n;i++) {
 increasingCnt[i] = search(0, upper_bound(vals.begin(), vals.end(), c[i]+x)-vals.begin()-1)+1;
 update(lower_bound(vals.begin(), vals.end(), c[i])-vals.begin(), increasingCnt[i]);
 }

memset(arr, 0, sizeof arr);
    for(int i=n-1;i>=0;i--) {
        decreasingCnt[i] = search(0, upper_bound(vals.begin(), vals.end(), c[i]+x)-vals.begin()-1)+1;
        update(lower_bound(vals.begin(), vals.end(), c[i])-vals.begin(), decreasingCnt[i]);
    }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<n;i++) {
 cin >> c[i];
 vals.push_back(c[i]);
 }
 sort(vals.begin(), vals.end());
 vals.erase(unique(vals.begin(), vals.end()), vals.end());
 while(_size<vals.size()) _size<<=1;
 _size<<=1;

int left=0, right=1e9;
 while(left<right) {
 int mid = left+right>>1;
 construct(mid);

bool chk=false;
 for(int i=0;i<n;i++) {
 if(n-(increasingCnt[i]+decreasingCnt[i]-1)<=m) {
 chk=true;
 break;
 }
 }
 if(chk) right=mid;
 else left=mid+1;
 }
 cout << left;
}
```