[ 백준 2631 ] 줄 세우기 (Java) - DP

---

🔗 문제 링크

2631번: 줄세우기

---

💡 문제 풀이 및 해석

1. 최소한의 인원을 이동시키면서 줄을 세워야 하는 문제이다.
2. 줄을 세운다 => 숫자를 정렬한다 => 정렬할 때, 최대한 적게 움직여야 한다.
3. 움직이는 인원 = 전체 - 움직이지 않아도 되는 인원
4. 움직이지 않아도 되는 인원 = 이미 줄이 제대로 돼있는 인원
5. 따라서 이미 정렬이 되어있는 인원을 전체에서 빼주면 된다!!
6. 내 위치에서 내 앞에 있는 인원들을 비교하여 나까지 증가하는 부분 수열을 구하면 된다.

---

⭐️ 정답 코드 및 설명

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    static ArrayList<Integer> list = new ArrayList<>();
    static int n;
    static int[] dp;
    static int answer = 0;

    static void init() {
        n = scanner.nextInt();
        dp = new int[n];
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }
    }

    static void sol() {
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 반드시 1명은 옮기지 않아도 된다.
            for (int j = 0; j <= i; j++) {
                // 맨 앞부터 본인까지 탐색하여 증가하는 부분 수열이 이루어진다면 교체한다. (큰 순서로)
                if (list.get(i) > list.get(j) && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, dp[i]); // 모든 경우에서 가장 큰 증가하는 부분 수열이 움직이지 않아도 되는 인원
        }
    }

    public static void main(String[] args) {
        init();
        sol();
        System.out.println(n - answer);
    }
}

---

🤔 문제 후기

문제의 해답을 '전체 - 움직이지 않아도 되는 인원' 보다는 그냥 '움직이는 인원의 최소값'을 찾아야 한다고 생각하였다. 그래서 줄에서 가장 줄이 엇나가 있는 인원 순서대로 (예를 들자면, 예제에서는 7 앞에는 6명이, 7 뒤에는 0 명이 있어야 하는데, 앞에는 2명이 뒤에는 5명이 있기 때문에, 우선순위가 높음.) 옮기면 될 것이라 생각했다. 하지만, 이는 정확하게 예외 처리를 할 수 없고, 명확한 근거가 없기 때문에 포기하였습니다. 결국 구글링을 통해 어떤 방식으로 접근해야 하는지 찾았고, 움직이지 않아도 되는 사람을 고르는 것으로 접근해야 한다는 것을 알게되어 풀게 되었습니다.