[Baekjoon Online Judge] 백준 2631번 줄세우기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2631번 줄세우기

(C++, Python)

(글쓴날 : 2020.04.24)

 

---

* Baekjoon Online Judge, 백준 2631번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2631번 줄세우기

---

1) 문제

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

2631번: 줄세우기

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

번호가 붙여진 아이들 N명이 주어지고, 번호가 오름차순이 되도록 아이들을 이동시킬 때 최소 이동 횟수를 구하는 문제입니다.

 

저의 경우, 동적 계획법과 이분 탐색을 적용하였으며, C++과 Python을 사용했습니다.

이 문제의 핵심은 최장 증가 부분 수열인 LIS를 구하는 것인데, 아이들을 최소 횟수로 이동시킨다는 뜻을 바꿔 말하면, 이미 오름차순으로 정렬되어 있는 아이들을 이동시키지 않아야 한다는 뜻이기 때문입니다.

LIS를 구하기 위해서는 동적 계획법으로만 구할 수도 있지만, memoization을 위해 시간 복잡도가 O(n²)이 되므로, 효율을 좋게 하기 위해 lower_bound 방식의 이분 탐색을 적용시켜 시간 복잡도를 O(n log n)으로 줄였습니다. (물론, O(n²)으로도 문제는 풀립니다!)

그렇게 LIS 즉, 이미 오름차순으로 정렬되어 있는 최대 길이를 구한 뒤, 전체 N에서 뺀 결과를 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int children[201];
 
int main(void)
{
    ios_base::sync_with_stdio;
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> children[i];
 
    vector<int> LIS;
    LIS.push_back(0);
    int length = 0;
 
    int left = 0;
    int right = 0;
    int mid = 0;
 
    for (int i = 0; i < N; i++)
    {
        if (children[i] > LIS[length])
        {
            LIS.push_back(children[i]);
            length++;
        }
        else
        {
            left = 0;
            right = length;
 
            while (left < right)
            {
                mid = (left + right) / 2;
 
                if (LIS[mid] >= children[i])
                    right = mid;
                else
                    left = mid + 1;
            }
 
            LIS[right] = children[i];
        }
    }
 
    cout << N - length;
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
children = [int(input())for _ in range(N)]
LIS = [0]
length = 0
 
for num in children:
    if num > LIS[-1]:
        LIS.append(num)
        length += 1
    else:
        left = 0
        right = len(LIS)
 
        while left < right:
            mid = (left + right) // 2
 
            if LIS[mid] >= num:
                right = mid
            else:
                left = mid + 1
        
        LIS[right] = num
 
print(N - length)

---