[맛있는물회] [파이썬] <백준 알고리즘> 2631번 "줄세우기" (LIS 알고리즘)

문제 조건

---

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

솔직히 첨에 어떻게 푸는지 감도 안왔다.

 

DP라는 힌트보고도 잘 모르겠더라.

 

그래서 조금 힌트를 얻어서 최장 길이 부분 수열 즉, LIS라는 힌트를 얻게되었다.

 

백준의 11053문제 (가장 긴 증가하는 부분 수열) 문제와 동일하다.

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

 

이참에 LIS 알고리즘을 한번 살펴보자

*LIS- Longest Increasing Subsequence

 

주어진 배열에서 가장 길게 증가하는 부분 수열을 찾아내는 알고리즘이다.

dp를 사용해서 메모이제이션 기법을 이용한다.

 

2포인터를 사용하는데 현재의 위치와 이전 위치의 값들을 비교해준다.

왼쪽에서 오른쪽으로 한칸씩 이동하는데 dp에 담긴 값의 의미는 현재 값까지 최장 길이 부분 수열은 무엇인가 이다.

 

예를 들어

3 7 5 2 6 1 4

에서 dp는

1 2 2 1 3 1 4가 된다.

 

왜냐하면

먼저 dp[0]은 1로 초기화 해주고

 

for i in range(1,n):

      for j in range(0,i):

         if arr[i] > arr[j]:

이렇게 i는 현재값, 그리고 비교 하는 부분은 이전의 값들 j = 0~i-1 이다.

만약 j의 값이 i의 값보다 작다면 증가하는 부분수열이 가능하다.

그렇다면 j 의 dp 값에 1칸 더한 것 만큼 길이가 가능하다는 의미이다.

 

따라서 가능한 j의 dp의 최대값을 구한 후 그 값에 1을 더해서 dp[i]에 대입한다.

 

이렇게 끝까지 가면 최대값을 찾을 수 있다.

 

소스코드

import sys
from collections import deque
input=sys.stdin.readline


if __name__ == "__main__":
   n=int(input())
   arr=[int(input()) for _ in range(n)]
   dp=[0 for _ in range(n)]
   dp[0]=1
   MAX=0
   for i in range(1,n):
      for j in range(0,i):
         if arr[i] > arr[j]:
            MAX = max(MAX,dp[j])
      dp[i]=MAX+1
      MAX=0
   print(n-max(dp)) 

 

*파이썬 문법 정리