[JAVA] 7570, 2631 줄 세우기

난이도

골드3, 골드4

 

알고리즘: DP

두 문제의 기본 조건은 같다. 1부터 N까지의 번호를 가진 아이들이 무작위 순서를 가지고 일렬로 서있다. 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구해야 하는 것도 같다. 다만 아이를 옮기는 방식이 다르다.

7570번: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.
2631번: 줄 서있는 어린이 중 한 명을 선택하여 다른 어린이와 자리를 바꾼다.

 

우선 2631번부터 보면, 아무 자리로 옮길 수 있으므로 이미 번호 순서대로 서있는 아이들을 제외한 나머지 아이들을 순서에 맞게 이동시키면 정답이다.

예를 들어 다음과 같은 N=6의 배열이 있다면 [3, 5, 6] 혹은 [1, 2, 4]가 이미 번호 순서대로 서있는 가장 긴 수열이다. 따라서 답은 6 - 3 = 3이다.

 

하지만 7570번에서는 조건이 더 까다로워졌다. 제일 앞이나 뒤의 자리로만 옮길 수 있다. 즉 위의 예시에서 [1, 2, 4]가 있다면 2와 4사이로 3이 와야 하지만 올 수 없다. 그렇다면 순서대로 서있으면서 + 인접한 위치와 번호가 1만 차이나는
(수열 중간에 수가 오지 않아도 되는) 가장 긴 수열을 구하면 된다.

위 예시에서는 [3, 4] 혹은 [1, 2] 혹은 [5, 6]이 이에 해당한다. 따라서 답은 6 - 2 = 4이다.

 

코드

2631번에서 구해야 하는 수열은 가장 긴 증가하는 부분 수열(LIS)이다. 그대로 쓰면 되므로 설명은 생략한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb;

    static int N;
    static int[] children, lis;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        children = new int[N];

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

        lis = new int[N];
        Arrays.fill(lis, Integer.MAX_VALUE);

        int lisIdx = 0;

        lis[lisIdx++] = children[0];

        for (int n = 1; n < N; n++) {
            if (children[n] > lis[lisIdx - 1]) {
                lis[lisIdx++] = children[n];
            } else {
                lis[binarySearch(0, lisIdx, children[n])] = children[n];
            }
        }

        bw.write(sb.append(N - lisIdx).toString());
        bw.flush();
    }

    private static int binarySearch(int left, int right, int key) {
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (lis[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

 

7570번은 현재 번호 이전에 와야할 번호가 정해져 있으므로 (현재 번호 - 1), 현재 번호가 이루는 최장 길이의 수열 = 이전 번호가 이루는 최장 길이의 수열 + 1 이다. 따라서 DP를 사용해 문제를 풀 수 있다.

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

public class BOJ7570 {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        final int N = Integer.parseInt(br.readLine());
        
        final int[] dp = new int[N + 1];
        st = new StringTokenizer(br.readLine());

        int maxLength = 0;
        
        while(st.hasMoreTokens()) {
            int curr = Integer.parseInt(st.nextToken());
            dp[curr] = dp[curr - 1] + 1;
            maxLength = Math.max(maxLength, dp[curr]);
        }

        bw.write(String.valueOf(N - maxLength));
        bw.flush();
    }
}