테페리넷

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

====== 줄 세우기 ======

===== 풀이 =====
  * 잘 관찰해보면, 연속된 숫자가 오름차순으로 나타나는 서브시퀀스를 찾으면, 나머지 숫자들을 앞이나 뒤로 이동시킴으로써 정렬된 배열을 만들수 있다는 것을 알수 있다. 결국, 연속된 숫자가 오름차순으로 나타나는 서브시퀀스중에서 가장 길이가 긴 것을 찾는 문제가 된다. 전체 길이에서 찾은 서브시퀀스의 길이를 뺀 값이 답이 된다.
  * 연속된 숫자가 오름차순으로 나타나는 서브시퀀스중 가장 길이가 긴 것을 찾는 방법은 DP를 사용한다. length[x] 를 x로 끝나는 서브 시퀀스의 최대 길이라고 하고, 처음에는 이값을 전부 0으로 초기화한다. 수열 A를 앞에서부터 이터레이션해서 얻은 A[i]에 대해서 length[A[i]] = length[A[i-1]]+ 1 로 업데이트 해주면 된다. 그러면 max(length)로 가장 긴 서브시퀀스의 길이를 찾을수 있다. 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 7570. 줄 세우기".

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

Tags: [Greedy] [DP]
"""


def main():
    N = int(input())
    nums = [int(x) for x in input().split()]

    lengths = [0] * (N + 1)
    for num in nums:
        lengths[num] = lengths[num - 1] + 1
    print(N - max(lengths))


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

{{tag>BOJ ps:problems:boj:골드_3}}