[ BOJ 백준 2631번 - 줄세우기 ] 해설 및 코드

https://www.acmicpc.net/problem/2631

 

 

목적

번호 순서에 맞게 줄을 다시 세울 때, 최소한의 아이들을 움직여 바로 세워보자.

 

접근법

1. LIS를 구한 후 N에서 빼자.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,c[200],ans=0,tmp;
    cin>>n;
    f(i,0,n){
        cin>>tmp;
        int idx=upper_bound(c, c+ans, tmp)-c;
        if(idx==ans)c[ans++]=tmp;
        else c[idx]=tmp;
    }
    cout<<n-ans;
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.