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

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

 

목적

맨 앞이나 맨 뒤로 이동시키는 어린이의 수를 최소로하여 n명의 어린이를 번호 순으로 줄 세우자.

 

접근법

1. 최적의 선택으로 어린이를 맨 앞이나 맨 뒤로 이동시키게 되면, 일련의 연속된 순서로 정렬이 되어야 할 것이다. 정렬 과정을 거꾸로 보자.

 

• 6명의 어린이가 있고 1명의 어린이만 맨 뒤로 보내면 되는 상황이다. 6번 어린이를 맨 뒤로 보냄으로써 1에서 5까지 연속된 배열의 길이가 1 증가하여 정렬이 마무리 된다.

 

• 이전 상황으로 1에서 4까지 일련의 연속된 배열이 있다. 이 배열의 길이를 증가시키기 위해선 2명의 어린이를 앞 또는 뒤로 이동시켜야 하고 5가 이동하여 1~5의 배열을 형성하게 된다.

 

• 한번 더 이전으로 가면 2에서 4까지의 연속된 배열을 볼 수 있다. 이 배열의 길이를 증가시키기 위해선 3명의 어린이를 이동시켜야하며 1번 어린이와 5번 어린이를 이동시킬 수 있다.

2. 바로 위의 상황에서 2,3,4,6을 이동시키지 않고 5나 1을 이동시킨 이유를 생각해보자. 어린이를 한번 이동시키면 1에서 6까지의 부분 배열의 길이를 1씩 증가시켜야 최소한의 이동으로 정렬을 할 수 있다. 즉, 가장 긴 연속된 배열의 길이를 증가시켜 나가야 최소한의 이동을 하게 되는 것이다.

 

3. 한번 이동으로 해당 배열의 길이가 1씩 증가하므로, 최소로 이동시켜야 하는 어린이의 수는 가장 긴 연속된 배열의 길이에서 어린이의 수를 빼면 된다.

 

4. 따라서 연속된 LIS를 구해야 하며, dp로 해결한다. p[i]는 i번 학생으로 끝나는 배열의 길이로, i-1번 학생으로 끝나는 배열의 길이(p[i-1])에서 1을 더한 값이다. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
int n,no,mx,p[(int)1e6+1];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    f(i,0,n){
        cin>>no;
        mx=max(mx,p[no]=p[no-1]+1);
    }
    cout<<n-mx;
    return 0;
}
 

 

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

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