[백준 알고리즘] 7570번: 줄 세우기 (JAVA)

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

7570번: 줄 세우기

 

---

소스코드

package Baekjoon.DP;
import java.io.*;
import java.util.*;

class P7570 {
    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		// 뽑은 수를 맨 뒤와 앞으로만 이동시킬 수 있기 때문에, 증가하는 부분수열은 연속적이어야 함 !
		// 그게 아니라 아무데나 집어넣을 수 있으면 연속적이지 않아도 됨. 
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+1];

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

        sb.append(N-Arrays.stream(dp).max().getAsInt());
        System.out.println(sb);
        
	}
}

 

 

---

풀이

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

2631번: 줄세우기

 

★  위 문제와 비슷한 유형의 문제이지만 이동하는 학생이 아무데나 갈 수 있는 것이 아니라, 줄의 맨 앞과 뒤로만 이동할 수 있다는 점이 차이입니다. 이는 곧 증가하는 부분 수열이지만, 연속적인 수를 가져야 한다는 의미입니다 ! 

 

예시로, 5 2 4 1 3이 주어진 경우, 2와 3은 움직이지 않고 5, 4, 1만 맨 앞, 뒤로 보내면서 조건을 만족하는 수열을 만들 수 있습니다 ! 이때 dp의 인덱스는 0번부터 시작하는 것이 아니라, 수열의 값이 dp의 인덱스가 됩니다. 그렇기에 자기 자신의 바로 전  dp의 값이 +1을 한 값이 자신의 dp 값이 됩니다 !