백준 7570번 줄 세우기 :: 마이구미

이 글은 백준 알고리즘 문제 7570번 "줄 세우기" 를 풀이한다.

정올 초등부, 중등부에서 출제된 문제이다.

동적계획법과 구현을 통한 2가지 풀이를 다뤄본다.

문제 링크 - https://www.acmicpc.net/problem/7570 

예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄서 있다고 하자. 

5 2 4 1 3

위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다. 

(1) 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)

(2) 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)

(3) 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)

위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.

이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.

문제의 핵심은 맨 앞 또는 맨 뒤로 학생을 보낼 수 있다는 것이다.

다음 예제를 보자.

4 2 1 3 5
=> 1 4 2 3 5
=> 1 2 3 5 4
=> 1 2 3 4 5

1을 맨 앞으로 옮긴다.

4를 맨 뒤로 옮긴다.

5를 맨 뒤로 옮긴다.

결과적으로 최솟값은 3이 나온다.

그렇다면 어떻게 최솟값을 구할 수 있을까?

LIS(가장 긴 증가수열) 알고리즘을 알고 있다면, 조금 더 빨리 해결했을 것이다. (LIS 알고리즘)

기본적인 LIS 알고리즘 문제로는 2605번 줄 세우기 문제가 존재한다.

2631번과 7570번은 비슷해보이지만 차이점은 있다.

2631번 문제의 경우에는 맨 앞, 맨 뒤 구별없이 어느 곳이든 보낼 수 있다.

7570번 문제의 경우에는 맨 앞, 맨 뒤만 보낼 수 있다.

2631번의 문제라고 가정한다면, 가장 긴 증가수열을 구하면 2 3 5 또는 1 3 5 가 나온다. (2631번 줄 세우기 풀이)

증가수열에 포함하는 번호는 고정한 채 나머지 번호만 움직이면 되기 때문에, 나머지 번호의 갯수만큼 이동하면 되기 때문에 쉽게 풀 수 있다.

4 2 1 3 5
=> 2 3 5

가장 긴 증가수열의 길이는 3 이기에, 나머지 번호의 갯수인 즉, 최솟값은 2가 된다.

답이 맞지 않는 것을 알 수 있다.

그 이유는 7570번은 어느 곳이든 보낼 수 있는 것이 아니라 맨 앞과 맨 뒤에만 보낼 수 있다.

그렇기에 가장 긴 증가수열에 포함하지 않는 나머지 번호들의 움직임이 자유롭지 않기 때문이다.

위의 예시를 다시 살펴보면, 1 4 5 가 이동했다는 것을 알 수 있다.

2와 3은 고정적이고 1 4 5가 움직였다는 의미가 된다.

4 2 1 3 5

결론적으로 가장 긴 증가수열을 찾되 연속된 수를 가진 증가수열을 찾으면 문제를 해결할 수 있다.

단순히 이중 반복문을 통해 찾는다면, n의 수가 1000000개 이기에 시간 초과를 낸다.

각 번호에 대한 인덱스를 통해 해결한다면 O(n^2) 은 피할 수 있게 된다.

1을 더한 수의 위치가 본인보다 뒤에 있어야만 연속된 증가수열이라는 것을 이용하면 된다.

for (int i = 1; i <= n; i++) {
    array[i] = sc.nextInt();
    position[array[i]] = i;
}
// pi - 기준이 되는 번호의 어린이 위치, ni - 다음에 있는 어린이 번호의 위치
for (int i = 1; i <= n - 1; i++) {
    int p = array[i] + 1;
    int ni = position[p];
    int pi = i;
    int temp = 1;

    while (ni > pi) {
        pi = position[p];
        ni = position[++p];
        temp++;
    }
    if (temp > len) {
        len = temp;
    }
}

위 방식보다 효율적인 수열을 찾는 방식으로는 동적계획법으로 접근할 수 있다.

문제 풀이에 대한 접근법은 같되 구현 방법이 다를 뿐이기에, 동적계획법이 아직 익숙하지 않다면, 첫번째 방법을 이해해도 무방하다.

점화식은 다음과 같다.

dp[n] = n번호일때까지 연속된 증가수열의 개수
=> dp[n] = dp[n - 1] + 1

Github - https://github.com/hotehrud/acmicpc/tree/master/lis

private void solve() {
        // 가장 긴 증가 수열, but 증가하는 수가 연속적 증가하여야한다.
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        int max = 0;
        // dp[i] = i번호일때까지 연속된 증가수열의 개수
        // dp[i] = dp[i - 1] + 1;
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            dp[k] = dp[k - 1] + 1;
            max = Math.max(dp[k], dp[k - 1] + 1);
        }
        System.out.println(n - max);
}