문제

풀이

이 문제를 풀기 위한 핵심은,

LIS를 구하되, LIS의 원소가 연속하여야 한다는 것이다.

나는 15분 정도 문제를 들여다보다가 처음 보는 유형이라 시간이 엄청 많이 걸릴 것을 직감하고 풀이를 찾아봤다ㅎ

위 문제에서 주어지는 5 2 4 1 3 의 풀이의 경우, 원소가 연속하는 LIS인 '2-3'를 고정시키고 나머지 원소인 1,4,5를 이동시키는 것을 확인할 수 있다.

이처럼 LIS의 원소들은 고정시키고, 다른 원소들을 이동시키면 무조건 답을 도출해낼 수 있다.
따라서 원소가 연속하는 LIS의 길이를 알아내면 된다.

첫 번째 풀이 방법

참고 블로그

package lis;

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

public class Boj7570_줄세우기 {
    static int[] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];
        for(int i=1; i<=N; i++) {
            arr[Integer.parseInt(st.nextToken())] = i;
        }

        // LIS를 구한다. 단,  ** LIS의 원소들은 연속하여야 한다. **
        int max = 1;
        int cnt = 0;
        for(int i=2; i<=N; i++) {
            if(arr[i] > arr[i-1]) {
                if(++cnt > max) {
                    max = cnt;
                }
            } else {
                cnt = 1;
            }
        }
        System.out.println(N-max);
    }
}

이 방법은 LIS의 컨셉을 기반으로 하지만, 코드엔 적용되지 않는다.
int[] arr에서 arr[i]는 해당 숫자를 가진 어린이의 줄에서의 위치를 나타낸다.
즉, 5 2 4 1 3가 주어질 때 arr[1]은 4가 된다. 1번이 4번째 순서에 있기 때문이다.

이제 숫자는 무조건 뒤로 갈수록 위치한 위치가 커져야 하므로, 연속해서 커지는 수열의 최대 길이를 구하기만 하면 된다.