[백준] 7570. 줄 세우기

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

 

처음에 떠올렸던 풀이는 시간 초과로 불가능했다. 따라서 다른 방법을 떠올려야 하는데, 구글링을 통해 dp로 O(N)의 시간으로 풀 수 있는 방법을 발견했다. (https://mygumi.tistory.com/276#recentEntries)

• 우선 숫자를 제일 앞이나 뒤로 이동시키는 최솟값 = (n - 가장 긴 연속된 숫자의 오름차순 수열의 길이)이다.
• 그리고 가장 긴 연속된 숫자의 오름차순 수열의 길이를 찾기 위해선 다음 점화식이 사용된다.
  • dp[n] = dp[n - 1] + 1

혼자 힘으로 떠올리기 힘들고 이렇게 적어도 와닿지 않지만, 예시를 통해 직접 적어가며 생각하면 이해는 된다..

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] dp = new int[n + 1];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            dp[num] = dp[num - 1] + 1;
            max = Math.max(max, dp[num]);
        }

        System.out.println(n - max);
    }
}