BOJ 2631 줄세우기

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

문제

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

---

출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

---

예제 입력 1

7
3
7
5
2
6
1
4

예제 출력 1

4

---

코드

브루트포스로 어느 아이를 어느 위치에 넣을지 이 모든 경우를 탐색하기엔 너무 탐색 수가 많아 불가능할 거 같아서 그리디나 DP로 풀 수 있을만한 규칙을 찾아보았다.

하지만, 아무리 생각해도 뭔가 규칙성이 보이지 않는 것이다…

결국, 구글링을 해봤다.

요점은 아이들의 번호가 가장 긴 증가하는 부분 수열을 이루는 아이들을 찾고 나머지 아이들을 이동시키는 것이다.

즉, 아이들의 수 N에서 가장 긴 증가하는 부분 수열의 길이를 빼면 그것이 정답이라는 말이다.

가장 긴 증가하는 부분 수열은 아래 문제들에 잘 설명돼있다.

BOJ 11053 가장 긴 증가하는 부분 수열

BOJ 11053 가장 긴 증가하는 부분 수열 2

이 문제에서는 N이 200 이하의 정수이기 때문에, 가장 긴 증가하는 부분 수열 문제의 알고리즘을 사용해도 정답일 것 같지만, 아래 풀이는 조금 더 효율적인 가장 긴 증가하는 부분 수열 2의 알고리즘을 사용했다.

역시… 정답 비율이 높으면 풀이 알고리즘을 생각해내기가 힘든 편인 것 같은데, 괜히 정답 비율이 65%가 아닌 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] increasingSubsequence;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] children = new int[N];
        for (int i = 0; i < N; i++) {
            children[i] = Integer.parseInt(br.readLine());
        }

        increasingSubsequence = new int[N];
        int lastIdx = 0;
        increasingSubsequence[0] = children[0];

        for(int i = 1; i < N; i++) {
            // 만약 현재 탐색 값이 증가하는 부분수열의 마지막 값보다 크다면 원소 추가
            if(children[i] > increasingSubsequence[lastIdx]) {
                lastIdx++;
                increasingSubsequence[lastIdx] = children[i];
            } else {
                int replaceIndex = lowerBound(children[i], 0, lastIdx);
                // 대체 할 인덱스의 값을 children[i]로 대체한다.
                increasingSubsequence[replaceIndex] = children[i];
            }
        }

        System.out.println(N - (lastIdx + 1));
    }

    // 이분 탐색을 활용하여 key보다 큰 값 중 가장 가깝거나를 key와 같은 값의 인덱스를 탐색
    static int lowerBound(int key, int s, int e) {
        if(s == e) {
            return s;
        }

        int mid = (s + e) / 2;
        if (increasingSubsequence[mid] < key)
            return lowerBound(key, mid + 1, e);
        return lowerBound(key, s, mid);
    }
}