[백준 / BOJ] 2631번 : 줄세우기 (JAVA)

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

2631번: 줄세우기

LIS

사실 이 문제는 어떻게 풀어야 하는지 전혀 개념이 안 떠올라서 힌트를 보고 풀었다. 기본 아이디어가 어떻게 되는지 찾아봤는데 배열에서 증가하는 가장 긴 부분 수열을 구하는 것이었다. 이를 LIS : Longest Increasing Subsequence 라 부른다. 예컨데 다음과 같다.

3 1 5 6 4 7 2

라는 숫자 배열이 있을 때 LIS는

3 5 6 7

이다. 3 1 5 6 4 7 2 이기 때문이다. 증가하는 수열이 꼭 위치까지 연속해서 나타날 필요는 없다.

 

왜 LIS 문제냐면, 아이 둘을 스위칭하는 것도 아니고 원하는 자리에 바로 데려갈 수 있으니 순서대로(증가하는 숫자대로) 서 있는 아이들을 제외하고 이리저리 섞인 아이의 위치만 바로잡아주면 되기 때문이다.

 

실제 LIS를 어떻게 구하는지는 모르지만 나름대로 코드를 작성해보았다. 증가하는 연속 수열이 몇 개인지 작성하는 cost라는 배열을 새로 만들고, 각 아이가 나올 때마다 그 아이의 번호보다 작은 부분을 탐색하여 가장 큰 값을 가져왔다. 5번을 가진 아이가 나오면 cost의 1부터 4까지를 탐색하고 그 중 가장 큰 값 + 1을 cost의 5번에 넣어주는 것이다.

 

매번 for문을 처음부터 돌리는 게 비효율적으로 느껴졌지만 다음에 어느 기준으로 max값을 찾을지 알 수 없는데다가 cost 내부를 max 값으로 채운다면 그 때도 for문이 필요하기 때문에 매번 탐색하도록 제출했다. N이 최대 200이기 때문에 연산은 최대 40,000으로 시간 초과를 내진 않았다.

 

전체 코드

// 시간 : 76ms
// 메모리 : 11516KB
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] children = new int[N];
		int[] cost = new int[N + 1];
		
		for (int i = 0; i < N; i++) {
			children[i] = Integer.parseInt(br.readLine());
		}
		
		int r = 0;
		for (int i = 0; i < N; i++) {
			int max = 0;
			for (int j = 0; j < children[i]; j++) {
				if(max < cost[j]) {
					max = cost[j];
				}
			}
			cost[children[i]] = max + 1;
			if(r < cost[children[i]]) r = cost[children[i]];	
		}
		
		System.out.println(N - r);
	}

}