BOJ 7570 - 줄 세우기

문제

1부터 N까지의 순열이 주어질 때, 앞이나 뒤로 이동하여 오름차순으로 만드는 최소 이동 횟수를 구하라.

입력

첫째 줄에 N, 둘째 줄에 순열이 주어진다.

출력

최소 이동 횟수를 출력한다.

예제

입력	출력
`5` `5 2 4 1 3`	`2`

풀이

DP로 "연속 증가하는 가장 긴 부분 수열"의 길이를 구하고, N에서 빼면 답이다.

dp[i] = i-1번 값의 dp + 1로 "값이 연속으로 증가하는 가장 긴 체인"을 추적한다
이 체인에 포함되지 않은 원소만 이동하면 된다
답 = N - max(dp[i])

핵심 아이디어: 연속 증가하는 가장 긴 부분 수열의 원소들은 이동하지 않아도 되며, 나머지만 이동하면 최소이다.

코드

package day699;
 
import java.io.*;
import java.util.*;
 
public class Day662BOJ7570줄세우기 {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    int n = Integer.parseInt(br.readLine());
 
    int[] dp = new int[n + 1];
    int max = 0;
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      int idx = Integer.parseInt(st.nextToken());
      dp[idx] = dp[idx - 1] + 1;
      max = Math.max(max, dp[idx]);
    }
 
    System.out.println(n - max);
    br.close();
  }
}

복잡도

시간: O(N)
공간: O(N)

문제