• 백준 7570번 줄 세우기 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 12. 24. 18:42
    반응형

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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);
    }
    cs


    반응형

    댓글

Designed by Tistory.