백준 2631번 <줄세우기>

백준 알고리즘 2631번

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

2631번: 줄세우기

---

2631번

1부터 N 까지 번호표를 붙인 아이들이 있다. 처음엔 오름차순대로 걸어갔지만 걷다보니 순서가 바뀌었다. 바뀐 순서에서 원래 오름차순 순서로 돌아오기 위해 최소한의 아이들만 움직이고 싶다. 최소 몇 번 움직여야 하는지 구하여라.

 

입력으로 첫 줄에 아이들의 수인 N이 들어오고 그 다음 N개의 줄에 걸쳐 현재 순서가 어떻게 되는지 들어온다.

 

출력으로 오름차순 순서로 바꾸기 위해 최소 몇 명이 움직여야 하는지 구해 출력하면 된다.

---

문제 해결

처음에 어떻게 풀어야 하는지 조금 고민했는데 최대한 아이들을 건드리지 않는 방법을 생각했다.

그러기 위해서는 최장 증가 부분 수열을 구해야 한다는 것을 깨달았다. 최장 증가 부분 수열로 이루어진 아이들은 건드리지 않고 거기에 속하지 못하는 아이들을 움직여주면 된다.

 

아이들의 수는 최대 200이기 때문에 최장 증가 부분 수열은 아래와 같이 구했다.

 

DP[i] : i번 친구를 가장 마지막으로 하는 최장 증가 부분 수열의 길이

0부터 i-1까지 for문(j)을 돌면서 j번 친구의 번호가 i번 친구의 번호보다 작다면

j번 친구를 가장 마지막으로 하는 최장 증가 부분 수열의 뒤에 i번 친구를 세울 수 있으므로 DP[j-1]+1이 DP[i]의 값이 된다.

이때 DP[i]의 원래 값과 비교하여 더 클 경우에만  update 해준다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class BOJ_2631 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());    // N : 아이들의 수
        int[] children = new int[N];    // children[i] : i번째 위치에 있는 아이
        int[] DP = new int[N];          // DP[i] : i번을 마지막 원소로 하는 최장 증가 부분 수열의 길이
        for (int i = 0; i < N; i++) {
            children[i] = Integer.parseInt(br.readLine());
            DP[i] = 1;
        }
        // end input

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++){
                if (children[j] < children[i]){     // j번째 친구가 i번째 친구보다 작다면
                    // j번을 마지막으로 하는 최장 증가 부분 수열에 children[i]를 붙일 수 있으므로
                    // 기존 DP[i]값과 DP[j] + 1 값 중 큰 값이 DP[i] 의 값이 된다.
                    DP[i]= Math.max(DP[i], DP[j]+1);
                }
            }
        }
        int cnt = 0;
        for (int j = 0; j < N; j++){
            cnt = Math.max(cnt, DP[j]);
        }
        System.out.println(N - cnt);
    }
}

---

결과

 

---