테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 병사 배치하기 ======

===== 풀이 =====
  * 발상에 걸린 시간: 매우짧음 / 구현에 걸린 시간: 매우짧음
  * 그냥 문제를 읽으면 최장 감소 부분 수열의 길이를 구하라는 문제라는 것을 바로 알수 있다. 
  * 전체 길이에서 최장 감소 부분 수열의 길이를 뺀 값이 열외해야하는 최소 병사수가 된다. 
  * 최장 감소 부분 수열은, 수열을 뒤집어서 [[ps:가장 긴 증가하는 부분 수열]]을 구하면 간단하다. 시간복잡도는 O(nlogn).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 18353. 병사 배치하기".

- Problem link: https://www.acmicpc.net/problem/18353
- Solution link: http://www.teferi.net/ps/problems/boj/18353

Tags: [LIS]
"""

import bisect


def main():
    N = int(input())  # pylint: disable=unused-variable
    nums = [int(x) for x in input().split()]

    arr = []
    for num in reversed(nums):
        pos = bisect.bisect_left(arr, num)
        if pos == len(arr):
            arr.append(num)
        else:
            arr[pos] = num

    print(N - len(arr))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_2}}