[백준 2631번] 줄세우기 (python)

문제

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

 

 

기록

(dp 11일차) 가장 긴 부분증가수열을 구하면 해당되는 숫자는 순서에 맞게 자리한 수이기 때문에, 이외의 숫자들만 자리에 맞게 옮기면 최소횟수가 된다. 따라서 가장 긴 부분증가수열의 길이를 구하고, 전체 길이에서 빼주었다.

 

가장 긴 부분증가수열을 구하는 방법은, 각 n을 마지막으로 하는 증가수열의 길이를 저장하는 dp배열을 사용하여 점화식 dp[n] = max(dp[n 전의 n보다 작은 수들], , )+1을 사용하여 구하면 된다.

 

ex) 위의 예시 3 7 5 2 6 1 4 라고 할 때, 부분 증가 수열 구하기

1. 3을 마지막으로 하는 증가수열의 길이 (3보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1

2. 7을 마지막으로 하는 증가수열의 길이 (7보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2

3. 5를 마지막으로 하는 증가수열의 길이 (5보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2	2

4. 2를 마지막으로 하는 증가수열의 길이 (2보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2	2	1

5. 6을 마지막으로 하는 증가수열의 길이 (6보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2	2	1	3

6. 1을 마지막으로 하는 증가수열의 길이 (1보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2	2	1	3	1

7. 4를 마지막으로 하는 증가수열의 길이 (4보다 작은 수 중 가장 큰 증가수열의 길이+1)

3	7	5	2	6	1	4
1	2	2	1	3	1	2

가장 긴 부분 증가 수열은 3 5 6 이며 길이는 3이다. 따라서 이외의 수인 7, 2, 1, 4만 자리에 맞게 옮겨주면 된다.

 

코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [(0, 0)]*(N+1)
_max = 0
for i in range(1, N+1):
    n = int(input())
    for j in range(i):
        if dp[j][0]<n :
            dp[i] = (n, max(dp[j][1]+1, dp[i][1]))
            _max = max(_max, dp[i][1])
print(N-_max)

1. 각 수를 마지막으로 하는 부분증가수열의 길이를 (수열의 수, 부분증가수열 길이) 형태로 저장할 dp 배열 생성

2. 바깥 반복문은 수열의 수만큼, 안쪽 반복문은 자신보다 전의 원소를 돌면서 가장 큰 부분증가수열 길이를 찾아 1을 더하여 저장한다.

3. 전체 길이 N에서 가장 큰 부분증가수열 길이를 뺀 수를 출력한다.