[백준 2631] 줄 세우기

문제

어린이집에 N명의 학생이 있고 소풍을 가려고한다. N명의 학생에게 1번부터 N번까지 번호를 부착하였고 학생들을 보호하기위해 번호순서대로 일렬로 서서 걸어가도록 하였다. 중간에 학생들의 번호순서가 바뀌었다.

이때 학생들을 이동시켜서 원래 번호순서대로 다시 줄 세우기위해서는 최소한 몇 명의 학생을 이동시켜야하는지 구하라.

 

입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

 

출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

---

접근

예전에 크루스칼이나 프림을 적용하는 문제를 풀 때 최소신장트리를 구성해야한다는 것을 파악하면 쉽게 풀 수 있었다. 이번 문제에서도 LIS를 구하는 문제라고 파악을 하였다. 

 

왜냐하면 아이들은 처음에 1번부터 N번까지 오름차순으로 정렬되어있었고 다시 이상태로 복구를 시켜야하고 최소한의 아이들만 이동시켜야했다. 그렇다면 원래 정렬되어있는 아이들은 그대로두고 아닌 아이들을 이동시켜야한다. 이를 위해서는 LIS를 구하고 해당 아이들을 제외한 나머지 아이들을 이동시키도록 한다.

 

구현

- 이전의 LIS문제처럼 현재 i까지 봤을 때 가장 긴 오름차순 수열을 구하도록 한다.

- 이후 cache리스트에 각 i에 대한 오름차순 수열이 저장되어있으며

- 여기서 가장 큰 수를 구하여 N에서 빼주도록 한다.

for i in range(N):
    for j in range(i):
        if students[j] < students[i]:
            cache[i] = max(cache[j]+1, cache[i])

max_value = -1
for value in cache:
    if max_value < value:
        max_value = value

answer = N - max_value
print(answer)

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
students = []
cache = [1 for _ in range(N)]

for _ in range(N):
    number = int(input())
    number -= 1
    students.append(number)

for i in range(N):
    for j in range(i):
        if students[j] < students[i]:
            cache[i] = max(cache[j]+1, cache[i])

max_value = -1
for value in cache:
    if max_value < value:
        max_value = value

answer = N - max_value
print(answer)