Baekjoon 2631번 줄세우기

문제

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

걸린 시간

02 : 25 : 57

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int cache[200], S[200];

int lis(int start){
    // 메모이제이션
    int& ret = cache[start];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = 1;
    for(int next = start+1; next < n; next++)
        if(S[start] < S[next])
            ret = max(ret, 1+lis(next));
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> S[i];
    memset(cache, -1, sizeof(cache));
    int maxLen = 0;
    for(int begin = 0; begin < n; begin++)
        maxLen = max(maxLen, lis(begin));
    cout << n-maxLen << "\n";
    return 0;
}

옮기는 아이들의 수를 '최소'로 하는 최적화 문제이다. 제일 먼저 완전 탐색으로 접근해보았지만 각 단계마다 아이들의 순서를 직접 변경하는 것은 구현하기 어려울뿐더러 경우의 수도 너무 많을 것 같았다. 탐욕적인 방법으로도 해결해보려 했으나 정당성을 증명시킬 수 없었다.

포기하기 직전 마지막으로 지금까지와는 조금 다른 시각으로 문제를 바라보았다. 문제에서 설명한 대로 아이들을 직접 옮기는 것 말고 다른 방법이 있을 것이라고. 유형이 다른 dp 문제가 무엇이 있나 생각하던 중 최대 증가 부분 수열 문제가 떠올라, 순서가 바뀐 아이들을 수열로 생각해 최대 부분 증가 수열에 해당하는 값들을 제외하니 설명에서 이동시키는 아이들의 번호만 남게 되었다.

잠깐 덮어두었던 종만북 dp 단원 최대 증가 부분 수열 연습문제를 공부하고 ac를 받을 수 있었다.