[python] 백준 7570 줄 세우기

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

문제 해결

• 임의의 배열을 최소한의 이동을 통해 [i for i in range(n+1)] 를 만들면 된다.
• 이 말은 원소가 계속 증가 수열이 되도록 하면 된다는 것과 동치이다. (원소가 1~n까지 고정이므로)
• 이 문제를 보자마자 최대로 긴 증가 수열을 구하는 문제를 떠올렸다.
• 증가하다 끊긴 부분에서 두 원소 중 하나는 무조건 이동을 해야한다. 그리고 다시 증가하는 수열이 생겨도 원소 시이에 원소를 넣을 수 없기 때문에 병합 과정에서 한 수열은 의미가 없어진다. 따라서 가장 긴 증가수열을 구한 후 전체 개수에서 가장 긴 증가수열 원소의 개수를 빼주면 된다.
• 만약 한번도 바뀌지 않는 경우도 있다. 그 경우는 답을 0으로 출력한다.

 

CODE

n = int(input())
line = list(map(int, input().split()))
line.insert(0,0)

result = [0 for _ in range(n+1)]
for i in range(1,n+1):
    result[line[i]] = i

cnt = 1
max_length = -1

for i in range(1,n):
    if result[i] < result[i+1]:
        cnt += 1

        if cnt > max_length:
            max_length = cnt
    else:
        cnt = 1

print(n-max_length if max_length != -1 else 0)