백준 알고리즘 2631번: 줄 세우기

문제 정보

---

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

 

 

문제 파악

---

문제 조건

2 <= N <= 200

 

문제 내용

번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수 구하기

 

 

풀이

---

생각했던 내용

어떤 식으로 이 문제를 풀어가야 할까 고민을 많이 했지만, 생각이 쉽게 떠오르지 않아 다른 분들의 풀이를 참고하게 되었다

문제의 설명에 직접 수를 정렬하는 것처럼 되어 있어서 헷갈릴 가능성이 매우 높지만, 막상 풀고 나니 설명 안에 뜻이 담겨있다고 느꼈다

 

예제 )

3 7 5 2 6 1 4

예제에서는 해당 수들 가운데 4명의 아이들을 골라 정렬시킨다

첫번째로 4번, 두번째로 7번, 세번째로 1번, 네번째로 2번

 

공통점은 다음과 같은데, 위 4명의 아이들을 제외하고 아이들의 줄을 확인해 보면

3 7 5 2 6 1 4

 

3, 5, 6 의 아이들은 이미 정렬되어 있는 상태이다. 또한 더 중요한 점은 해당 아이들이 이루는 정렬된 부분 수열의 길이가 전체에서 최대라는 것이다.

 

3 7 5 2 6 1 4

여기서 더 찾아보아도, (3, 5, 6) 보다 길이가 긴 정렬된 부분 수열은 찾을 수 없다

 

따라서 이미 정렬된 부분은 제외한 나머지 부분만을 옮기게 된다면, 최소한으로 옮기고 만들어낸 정렬된 수열이 된다는 것이다

 

풀이한 내용

dp(다이나믹 프로그래밍)을 통하여, 각 위치의 아이들에서 가지는 부분 수열의 최대 길이를 구한다.

dp[i] = 0번째부터 i번째까지 아이들 중, i번째 아이를 포함했을 때 나타낼 수 있는 부분 수열의 최대 길이

 

// num[n] : 초기 아이들이 서있는 배열
// dp[n] : 각 위치의 아이들이 가지는 부분 수열의 최대 길이

for(i: 0 to n)
	dp[i] = 1	// 자기 자신을 포함하기 때문에, 부분 수열의 최소 길이는 1이다
	for(j: 0 to i)
    	if(num[j] < num[i]) // 만약 해당 위치(i) 이전의 값(j)이 더 작다면
        	dp[i] = max(dp[i], dp[j]+1) // 이전 위치의 부분 수열의 길이 + 1과, 가지고 있는 값 중 최대를 선택

 

 

코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        int max = 0;
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (numbers[j] < numbers[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(N - max);
    }
}

 

 

Source Code on GitHub

---