[Java] 백준 2631번 : 줄세우기*

1. 문제

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

2631번: 줄세우기

 

 

2. 풀이 과정

최대한 원래 줄을 안 건드리고 새로 줄 세우는 방법이 가장 빠르다. 따라서 원래 줄 중에서 가장 긴 부분 수열(LIS, Longest Increasing Subsequence)을 찾으면 된다. 결괏값은 전체 아이들의 수인 N - 가장 긴 부분 수열의 길이가 된다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] line = new int[N];
        int[] result = new int[N + 1];
        int len = 0;

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

        for(int i=0; i<N; i++){
            if(result[len] < line[i]){
                result[++len] = line[i];
            }
            else{
                int l = 0, r = len;
                while(l<r){
                    int mid = (l+r)/2;
                    if(result[mid] < line[i]){
                        l = mid + 1;
                    }
                    else{
                        r = mid;
                    }
                }
                result[l] = line[i];
            }
        }
        System.out.println(N-len);
    }

}

데이터가 적다면 아래 방법처럼 이중 반문 + DP로 구현하는 것도 괜찮아 보인다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] line = new int[N];
        int[] lis = new int[N];
        int result = 0;

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

        for(int i=0; i<N; i++){
            int max = 0;
            for(int j=0; j<i; j++){
                if(line[j] < line[i]){
                    max = Math.max(max, lis[j]);
                }
            }
            lis[i] = max + 1;
            result = Math.max(result, lis[i]);
        }
        System.out.println(N-result);
    }

}

 

 

결과