[JAVA] 백준 7570번 : 줄 세우기

 

 

---

 

• 생각

일전에 풀었던 LIS 알고리즘을 사용하여 풀었던 기억이 있어서 풀어보았지만 시간 초과가 나왔다.

 

DP로 하는 다른 방법이 생각이 나지않아서 코드를 찾아 보았다. mygumi.tistory.com/276를 토대로 이해한 결과로 코드를 작성하였다.

 

• 코드

정답 코드 : 점화식을 찾은 뒤 구현

 

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

public class Main {
	static int N, max;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(N-max);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        max = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
        	int temp = Integer.parseInt(st.nextToken());
            dp[temp] = dp[temp-1]+1;
            max = Math.max(max, dp[temp]);
        }
	}
}