[BOJ] 2631번. 줄 세우기 - JAVA

🌱 문제 링크

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

2631번: 줄세우기

 

📝 풀이 과정

풀이

문제 유형 : DP

 

이 문제는 어린이들을 정렬해야 하는 문제이다. 

중요한 건 이미 순서를 지키고 있는 어린이들은 옮길 필요가 없다. 예를 들어, 12435 순서대로 서있다면 1245 인 어린이들은 위치를 바꿀 필요가 없고 3 어린이만 위치를 바꾸면 된다. 이를 풀기 위해 필요한 개념이

LIS(Longest Increasing SubSequence) 알고리즘이다.

가장 긴 증가하는 부분 수열인데, 말 그대로 수가 증가하는 부분수열 중에 가장 긴 수열을 구하는 알고리즘이다.

이 수를 구해서 전체 인원수에서 빼면 최소로 이동하는 어린이의 수가 나온다.

 

시간 복잡도 : O(n^2) 

 

* LIS 알고리즘

ex) 12435라면

1. 1->2->4->3->5 순서대로 반복을 돌림

2. 처음엔 자기 자신 1개이므로 dp에 1 을 저장

3. 처음부터 자기 자신 직전까지 숫자를 비교하며 자기가 더 크다면 ( 증가한다. ) dp 에 저장된 값을 비교한다.

4. 현재 dp에 저장된 수보다 비교 숫자의 dp+1값이 더 크다면 갱신한다. (증가하는 숫자가 더 많다.)

5. 반복문을 모두 돌았다면 dp 에 저장된 값들 중에 가장 큰 값이 LIS 값이다.

 

느낀점

이런 방식의 풀이과정은 어떻게 생각해내는건지 모르겠다... 

 

💻 코드

import java.io.*;
import java.util.*;
 
 
/*
 * 어린이들을 정렬하는 문제
 * 이미 제자리에 있는 어린이들은 위치를 바꿀 필요가 없음
 * LIS(Longest Increasing SubSequence)를 구해서(=제자리에 있는 어린이들) 전체 인원수에서 빼면 이동할 어린이의 수
 */
 
public class Main_bj_2631_줄세우기 {
 
    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("res/input_bj_2631.txt"));
        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());
        }
        
        int[] dp = new int[N];                                // LIS
        int max=0;
        for(int i=0; i<N; i++) {
            dp[i] = 1;
            
            for(int j=0; j<i; j++) {
                if(children[j] < children[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(N-max);
        br.close();
 
    }
 
}
 

 

 

📌 채점 결과