[백준] 2631번: 줄세우기

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

2631번: 줄세우기

처음에 보면 당황스러운 문제일 수 있다.

문제 경험이 많이 없다면 이거 어떤 아이를 어디로 옮기는지 브루트 포스로 풀어야 하는지 감조다 찬 올 수 있다.

하지만 문제를 조금씩 풀다보면 상당히 익숙한 느낌을 지울 수 없다.

분명 나는 이전에 비슷한 문제를 푼 적이 있단 말이다!!

 

그래서 움직이는 아이와 움직이지 않는 아이를 따로 표시해보니, 무슨 알고리즘을 써야하는지 감이 왔다.

바로 증가하는 수열의 최대 길이(최장 증가 부분 수열, LIS)를 찾는 문제이다.

결과적으로 리턴하는 값은 전체 길이에서 해당 수열의 길이를 빼면 된다.

 

이 수열의 길이를 구하는 방법은 크게 두 가지가 있다.

약간 비효율적인 방법과, 비교적 효율적인 다이나믹 프로그래밍 방식이 있다.

처음에는 다이나믹 프로그래밍 방식을 떠올렸으나 전체 최대 길이가 200밖에 되지 않아서 그럴 필요까진 없는 것 같아서

전체를 탐색하는 비효율적인 방식으로 문제를 풀었다. 다행히 잘 통과가 되더라.

그래도 추후 더 난이도를 높여, 시간 복잡도가 높아질 경우를 대비해 두 방식 모두 알아보도록 하자.

 

1) O(N^2)

N개의 수들에 대해 자기 자신의 전의 모든 수를 훑어봐야한다.

여기서 나는 0 인덱스를 따로 빼지 않고, -1로 초기화한 다음 만약 해당 값보다 적은 값이 이전에 없으면 갱신하는 방식을 택했다.

하지만 알고리즘을 깔끔하게 짜기 위해서, 0인덱스는 0으로 채우고 1인덱스부터 값을 채우면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int find_len(int n, vector<int> nums) {
    int answer = 1;
    vector<int> result(n, -1);
    result[0] = 1;
    for(int i = 1;i < n;i++) {
        for(int j = 0;j < i;j++) {
            if(nums[i] > nums[j]) {
                if(result[j] + 1 > result[i]) {
                    result[i] = result[j] + 1;
                }
            }
        }

        if(result[i] == -1) {
            result[i] = 1;
        }

        answer = max(answer, result[i]);
    }

    return answer;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0;i < n;i++) {
        cin >> nums[i];
    }

    int len = find_len(n, nums);

    cout << n - len << '\n';
    return 0;
}

 

2) O(NlogN)

1번처럼 문제를 풀다보면 자연스레 의문이 든다.

자꾸 중복된 부분을 확인하는 절차가 길다.

최장 길이를 기록하는 D[i]를 계산하기 위해 A[0] ~ A[i - 1]을 꼭 다 훑어봐야 하는가?

만약 D[j] = k를 만족하는 j 중 A[j]의 값이 가장 작은 j만 어딘가에 저장해놓으면, 나중에 D[i]를 계산할 때 그 값들만 참조하면 D[i]의 값을 쉽게 알 수 있다.

 

예를 들어 3, 5, 7, 9, 2, 1, 4, 8이라는 수열이 있을 때 9까지는 계속적으로 증가하기 때문에 

 

D[i]	0	1	2	3	4
A[i]	0	3	5	7	9

이런 식으로 정리가 된다.

 

하지만 그 다음에 i = 5(value → 2)일 때를 살펴보면 급격하게 고민되기 시작한다.

2는 0과 3 사이의 값이다.

그러므로 D[5] = 0 + 1 = 1이다.

X에서 D[i] = 1일 때의 A[i]의 값은 현재 3이나, A[5] = 2이므로 더 작은 2로 갱신해준다.

이 말은 증가부분수열의 길이가 1인 수열 중 끝이 3으로 끝나는 증가부분수열(기존 수열)과 끝이 2로 끝나는 증가부분수열(현재수열)이 있으므로, 이들 중 끝값이 더 작은 2를 X를 저장해 놓겠다는 것이다.

 

→ 쉽게 이해하자면, 어차피 같은 길이면 더 낮은 2로 채워서 현재까지의 최장 부분 수열을 갱신한다는 뜻

→ 그러면 뒤의 값들이 앞에 놓여져서 꼬이는 것 아니냐구? 어차피 넣을 때는 이전의 값들만 반영하고, 그렇게 길이만 구하면 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int find_len(int n, vector<int> nums) {
    vector<int> d = {0};
    vector<int> a = {0};

    for(int i = 1;i <= n;i++) {
        if(nums[i] > d[d.size() - 1]) {
            d.push_back(nums[i]);
            continue;
        }

        auto pos = lower_bound(d.begin(), d.end(), nums[i]);
        *pos = nums[i];
    }

    return d.size() - 1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for(int i = 1;i <= n;i++) {
        cin >> nums[i];
    }

    int len = find_len(n, nums);

    cout << n - len << '\n';
    return 0;
}

 

참고

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4