[백준] 2631번 줄 세우기 (파이썬)

 

문제

 

2631번: 줄세우기

 

 

 

정답 소스코드 (Python)

 

n=int(input())
arr=[]
for _ in range(n):arr.append(int(input()))
dp=[1]*(n+1)
lenth=0

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            if dp[i]<dp[j]+1:dp[i]=dp[j]+1

    if lenth<dp[i]:lenth=dp[i]

print(n-lenth)

 

 

풀이  (Python)

 

 

이 문제는 번호 대로 줄 세우기 위해서 옮겨야 하는 횟수를 측정하는 것이 아닌, 안 바꿔도 되는 번호의 개수를 파악해야 한다.

즉 안 바꿔도 되는 번호의 개수를 전체 인원의 수인  n에서 빼주게 된다면, 정답을 구할 수 있다.

 

 

Point 1)  LIS (최장 증가 부분 수열) 알고리즘 활용

 

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            if dp[i]<dp[j]+1:dp[i]=dp[j]+1

    if lenth<dp[i]:lenth=dp[i]

 

해당 i번째 인원 전까지 0~j번째를 토대로 arr [i]보다 작은 arr [j]가 있다면, 부분수열에 추가하는 방식으로 dp [i]에 dp [j]+1 값을 대입해 준다.

 

이후 최댓값 비교를 통해 lenth에 최댓값을 저장해 준다.

 

위와 같이 i를 0부터 끝까지 검사하게 된다면, lenth에는 가장 긴 증가하는 부분수열의 개수가 저장되기 때문에, 전체 수인 n에서 해당 lenth를 빼주면 정답을 구할 수 있게 된다.