[백준] 줄세우기 2631 C++

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

 

---

해설

줄세우기 문제이다.

어떻게 아이들을 옮기면 최소의 횟수로 정렬된 상태를 만들 수 있는지 묻는 문제이다.

직관적으로는 간단한데, 어떠한 기준으로 어떤 수를 옮길지 처음 풀면 알기가 굉장히 힘들다.

본인도 https://www.acmicpc.net/problem/7570 문제 풀다가 안 풀려서 해당 문제 부터 풀었다...ㅎㅎ

해당 문제는 LIS (Longest Increasing Subsequence) 문제이다.

가장 큰 증가하는 부분 수열의 길이만 구해주면 바로 풀린다.

근데 이 문제가 LIS라는것 자체를 생각해내는게 어렵다.

 

그럼 일단 왜 LIS인지 보자.

3 7 5 2 6 1 4 순으로 있을 때 최소의 이동 횟수를 구하려면 3 5 6 아이들은 이동시키지 말고 7 2 1 4번 아이들만 옮겨주면 최소의 이동 횟수가 나온다.

3 5 6은 이미 정렬되어 있기때문에 또 옮길 필요가 없는 것이다.

즉, LIS의 길이를 구해서 n - LIS의 길이를 해주면 정답이 된다.

 

본인은 LIS를 DP를 통해서 접근하였다.

문제의 조건 N <= 200이기 때문에 O(N^2)의 풀이와 O(NLogN) 풀이 두가지가 있다.

O(N^2)의 풀이는 이중 루프를 통해 LIS의 길이를 구하는 방식이고 NLogN은 이분 탐색을 통해 가능하다.

 

아래 코드가 3개가 있다. N^2, lower_bound를 사용한 풀이, 직접 구현한 이분 탐색으로 푼 풀이..

모든 코드를 보고 이해하는 것을 추천한다. 굿.

---

코드

 

N^2 풀이

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321

int n, arr[204], dp[204];

int main(void) 
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];

    fill(dp + 1, dp + 1 + n, 1);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);

    int _max = *max_element(dp + 1, dp + 1 + n);

    cout << n - _max;
}

// <내 생각 & 해설>
// 왜 LIS의 최대값을 n에서 빼나?
// 아이들을 움직이는 최소의 횟수를 구해야한다. 3 7 5 2 6 1 4 순으로 아이들이 있다면 3 5 6 번 아이들은 움직일 필요가 없다. 이미 정렬되어 있기 때문이다.
// 3 5 6 번 아이들을 제외하고 나머지 아이들만 움직여 주면된다. 3 5 6 은 LIS(가장 긴 증가하는 부분 수열)이다.
// 아이들 n명 중에서 LIS의 최대값을 빼주면 이게 아이들을 최소로 움직이는 정답이다.
// n의 최대값이 200이기 때문에 이중 for문으로 LIS 구해주어도 무리가 없다.

 

 

NLogN풀이

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321

int n, arr[204];

int main(void) 
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];

    vector<int> lis;
    
    for (int i = 1; i <= n; ++i)
    {
        auto iter = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (iter == lis.end())
            lis.push_back(arr[i]);
        else
            *iter = arr[i];
    }

    cout << n - lis.size();

}

// <내 생각 & 해설>
// https://www.acmicpc.net/source/share/102ac37220c94a87a090fc6817eeb878
// N^2로 풀었던 위의 풀이와 다르게 NLogN으로 푼 풀이이다.
// 정답은 맞지만 실제로 lis배열을 보면 3 5 6 순의 LIS배열은 아니다. 해당 문제는 최소 이동 횟수만 구하면 되기 때문에 문제될 것은 없는듯하다
// (물론 LIS5문제는 이렇게 풀면 틀림 배열하나 더 필요하다)

 

 

NLogN 풀이2

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321

int n, arr[204];

int main(void) 
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];

    vector<int> lis;
    
    for (int i = 1; i <= n; ++i)
    {
        if (lis.size() == 0 || lis.back() < arr[i])
            lis.push_back(arr[i]);
        else
        {
            int l = 0, r = lis.size() - 1;

            while (l < r)
            {
                int m = (l + r) / 2;

                if (lis[m] < arr[i])
                    l = m + 1;
                else
                    r = m;
            }

            lis[l] = arr[i];
        }
    }

    cout << n - lis.size();
}

// <내 생각 & 해설>
// https://www.acmicpc.net/source/share/e7fc760cce354136b9c73eabd9fa5a36
// 위 풀이에 이어서 lower_bound가 아닌 직접 이분 탐색을 만든 풀이다.