[코딩테스트][백준] 🔥 백준 2631번 "줄세우기" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

import sys
input=sys.stdin.readline

N=int(input())

arr=[]
for i in range(N):
    arr.append(int(input()))

dp=[1]*(N)

for i in range(N):
    for j in range(0,i):
        if arr[i]>arr[j]:
            dp[i]=max(dp[j]+1,dp[i])

print(N-max(dp))

N명의 아이들이 서있을 때 이를 줄세우는 최소 아이들의 이동 수를 찾는 것이다. 이 때 순서대로 서있는 아이들을 제외하고 나머지 아이들을 옮기면 되므로 LIS를 구하면 된다. 이를 전체 길이에서 빼주면 되는 것이다.

이렇게 Python로 백준의 "줄세우기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊