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

[백준] 2631. 줄세우기

 

📌 풀이 과정

이 문제의 핵심은 "최소한의 이동으로 아이들을 오름차순으로 정렬하는 것"이다.

• 현재 줄에서 이미 올바른 순서로 서 있는 아이들은 움직일 필요가 없다.
• 나머지 아이들만 적절한 위치로 옮기면 전체가 정렬된다.
• 따라서 "움직이지 않아도 되는 최대 아이 수"를 구하는 것이 관건임!!!!

 

💡 핵심 아이디어

여기서 가장 긴 증가 부분 수열(LIS) 개념을 활용하게 되면 굉장히 쉽게 풀리는데,

LIS에 포함된 아이들은 이미 올바른 상대적 위치에 있다는 것을 기억하면 된다.

 

예를 들어

현재 순서: [3, 7, 5, 2, 6, 1, 4]
LIS: [3, 5, 6] (길이 3)

[3, 5, 6]은 이미 증가하는 순서로 배치되어 있으니, 이 아이들은 그대로 두고 나머지 아이들(7, 2, 1, 4)만 적절한 위치에 배치하면 된다.

 

∴ 답 = 전체 아이 수 - LIS의 길이

 

🎯 알고리즘

dp[i] = child[i]를 마지막 원소로 하는 LIS의 길이

1. 각 위치에서 끝나는 가장 긴 증가 부분 수열의 길이를 DP로 계산
2. 전체에서 가장 긴 LIS의 길이를 구함
3. N - LIS길이가 최소 이동 횟수

 

✨ 제출 코드

메모리: 14092 KB

시간: 104 ms

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] child = new int[N];
        int[] dp = new int[N];

        for(int i = 0; i < N; i++){
            child[i] = Integer.parseInt(br.readLine());
        }

        int maxLIS = 0;  // 가장 긴 증가 부분 수열의 길이
        for(int i = 0; i < N; i++){
            dp[i] = 1;  // 자기 자신만으로 길이 1
            
            for(int j = 0; j < i; j++){
                if(child[j] < child[i] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                }
            }
            maxLIS = Math.max(maxLIS, dp[i]);
        }

        // 전체에서 LIS 길이를 빼면 움직여야 할 아이들의 수
        System.out.println(N - maxLIS);
    }
}