[백준] 2631번. 줄세우기(JAVA)

문제

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

---

풀이(42분)

import java.io.*;
import java.util.*;

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[] input = new int[N];
        for(int i=0;i<N;i++){
            input[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[N];
        dp[0] = 1;

        int ans = 0;
        for(int i=1;i<N;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(input[i]>input[j]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(N-ans);

    }
}

 

큐나 스택을 사용하는 등 다양한 자료구조를 통해 문제를 해결해보려고 하여 시간이 오래걸렸다.

계속 고민을 거듭하던 중 가장 긴 증가하는 부분 수열 문제를 떠올렸고, 이를 찾은 뒤 나머지를 하나씩 배치하면 된다는 것을 깨달았다.

 

따라서 LIS를 구하고, 이를 N에서 빼주면 된다.

 

LIS에 대해 잘 모르면 구글에 자바 LIS 를 검색해보자.https://sskl660.tistory.com/89 이분의 블로그에 자세히 정리되어있으니, 꼭 본인의 것으로 만드는게 좋을 것 같다.