[백준] 18353 병사 배치하기

18353번: 병사 배치하기

 

boj.kr

풀이

병사 리스트를 뒤집으면 결국 LIS(Longest Increasing Subsequence) 문제가 된다는 것을 알 수 있다. LIS 알고리즘은 크게 2가지 방법이 알려져있다. 하나는 동적 계획법을 사용해 O(n^2) 시간에 해결하는 방법, 또다른 하나는 이분 탐색(lower_bound)를 사용해 O(nlogn) 시간에 해결하는 방법이다. 아래의 코드에서는 이분 탐색을 활용해 O(nlogn)의 복잡도로 해결했다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> soldiers;

int get_lis() {
    if (n == 1) return 0;
    vector<int> lis;
    lis.push_back(soldiers[0]);

    for (int i = 1; i < n; i++) {
        if (lis[lis.size() - 1] < soldiers[i]) lis.push_back(soldiers[i]);
        else {
            auto it = lower_bound(lis.begin(), lis.end(), soldiers[i]);
            *it = soldiers[i];
        }
    }
    return n - lis.size();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    soldiers = vector<int>(n);
    for (int i = 0; i < n; i++)
        cin >> soldiers[i];
    reverse(soldiers.begin(), soldiers.end());
    cout << get_lis() << '\n';
    return 0;
}

Python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().rstrip())
soldiers = list(map(int, sys.stdin.readline().rstrip().split()))

soldiers.reverse()


def get_lis():
    if n == 1:
        return 0

    lis = [soldiers[0]]

    for i in range(1, n):
        if lis[-1] < soldiers[i]:
            lis.append(soldiers[i])
        else:
            idx = bisect_left(lis, soldiers[i])
            lis[idx] = soldiers[i]
    return n - len(lis)


print(get_lis())