백준 7570 : 줄 세우기

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

7570번: 줄 세우기

[ 문제풀이 ]

여러 가지 테스트 케이스를 시도해보면 결국 주어진 수열에서 가장 긴 증가하는 연속 수열을 찾는 문제이다.

dp 테이블을 다음과 같이 정의하자.

dp[i] : i번째 숫자의 연속 수열 길이

증가하는 연속 수열을 찾는 것이기 때문에 dp[i]가 증가하기 위해선 (i - 1)번째 숫자가 i번째 숫자보다 먼저 등장해야 한다. 또한, dp 테이블의 정의에 따라 dp[i - 1]에는 (i - 1)번째 숫자의 연속 수열 길이기 저장되어있을 것이다.

즉, 다음과 같은 점화식을 도출해낼 수 있다.

dp[i] = dp[i - 1] + 1

1부터 N까지 진행하면서 가장 큰 dp[i]를 찾아주면 해결할 수 있다.

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

public class Main {
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			//dp[i] : i번째 숫자의 연속 수열 길이
			int[] dp = new int[N + 1];
			int[] data = new int[N + 1];
			int maxLen = 0;
			for (int i = 1; i <= N; ++i) {
				data[i] = Integer.parseInt(st.nextToken());
				
				dp[data[i]] = dp[data[i] - 1] + 1;
				maxLen = Math.max(maxLen, dp[data[i]]);
			}
			bw.write((N - maxLen) + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}