[백준 - 7570] 줄 세우기 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, dp

입력

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하나씩 들어있다. 단, 어린이 수는 1이상 1,000,000이하의 정수로 제한되고, 어린이 수가 N이면 어린이들의 번호는 1부터 N까지의 정수이다.

출력

입력에서 주어진 어린이들의 줄에 대해 번호순서대로 줄을 세우기 위해 제일 앞이나 제일 뒤로 보내는 어린이 수의 최솟값을 출력해야 한다.

풀이

어린이를 이동시키는 최솟값을 구해야 한다.

그러면 불필요한 이동을 없애야 하는데, 전체 수열에서 1씩 증가하는 수열은 옮기지 않아도 된다.

예를 들어 5 2 4 1 3에서 2 -> 3은 1씩 증가하는 수열이기 때문에 굳이 옮길 필요가 없다. 그렇지만 그외 나머지 수열들은 무조건 한 번씩 옮겨야 한다.

만약 1씩 증가하는 수열이 여러 개라면 어떻게 해야 할까? 당연히 가장 긴 수열만을 두고, 나머지를 옮기는 것이 최솟값이 된다.

예를 들어 4 1 5 2 6 3 7 일 때 4 -> 5 -> 6 -> 7, 1 -> 2 -> 3 이렇게 수열이 있는데 긴 수열을 놔두면 3번만 옮기면 되므로 최적해다.

자, 그러면 전체 수열에서 1씩 증가하는 가장 긴 수열을 찾는게 목적이다. 여기서 dp가 사용된다.
1씩 증가하는 수열이기 때문에 현재 값 - 1이 전에 얼만큼 1씩 증가하는 수열의 길이를 가졌는지를 알면 된다. 그래서 dp[현재 값] = dp[현재 값 - 1] + 1 로 정의할 수 있다.

예를 들어
5 2 4 1 3을 앞에서부터 검사하면,

1. dp[5] = dp[4] + 1; // dp[4]는 전에 한번도 나오지 않았기 때문에 0이다.
2. dp[2] = dp[1] + 1;
3. dp[4] = dp[3] + 1;
4. dp[1] = dp[0] + 1;
5. dp[3] = dp[2] + 1; // dp[2]는 전에 한번 나왔기 때문에 1를 가지고 있다. 그래서 dp[3]은 2가된다.

그래서 1씩 증가하는 가장 긴 수열은 2 -> 3으로 N - 2 = 3이 최솟값이 된다.

시간 복잡도는 O(N)이다.

소스 코드

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

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(st.nextToken());
            dp[num] += dp[num - 1] + 1;
        }
        
        int maxLen = -1;
        for(int i=1; i<=N; i++) {
            if(dp[i] > maxLen) {
                maxLen = dp[i];
            }
        }
        
        System.out.println(N - maxLen);
    }
}