[백준] 2631 줄 세우기

문제

• 1~N번까지 아이들은 번호순서대로 일렬로 서서 걸어가기 시작했다.
• 이동 도중 아이들의 번호 순서가 바뀌어 다시 번호 순서대로 옮기려고 할 때, 최소의 몇 명의 아이를 움직여야 하는지 구하기
• 2 <= N < 200
  
  
  

 

풀이

• 연속해서 증가하고 있는 번호 배열을 기준으로 나머지 아이들을 옮긴다.
  즉, N - LIS 값이 최솟값이 된다. 

 

N = int(input())
line = [int(input()) for _ in range(N)]

# dp[i] : ~i번까지 중 LIS
dp = [1] * (N+1)
for i in range(1, N) :
    for j in range(i) :
        if line[j] < line[i] and dp[j]+1 > dp[i] :
            dp[i] = dp[j] + 1

print(N-max(dp))

 

References

• 백준 DP