백준 2631번 : 줄세우기 in Python

2631번: 줄세우기

 

www.acmicpc.net

이 문제는 N명의 아이들이 번호순서가 무작위로 바뀐 상태로 줄울 섰을 때 번호 순서대로 배치하기 위해 옮겨야 하는 아이들의 최소 수를 구하는 문제이다.

이를 효율적으로 해결하기 위해서는 우선 그나마 제대로 줄을 선 아이들을 고정시키고, 나머지 아이들을 이 아이들 사이에 넣어야 한다. 예를 들어 아이들이 3 7 5 2 6 1 4 순서로 줄을 섰다고 가정하면 3, 7번 아이들이 그나마 번호 순서대로 섰기에 이를 고정시킨 뒤 나머지 5, 2, 6, 1, 4번 아이들을 순서에 맞게 넣으면 된다. 이 밖에도 3, 5, 6번 아이들을 고정시킨다던가, 2, 4번 아이들을 고정시키는 방법도 있다.

이때 이동하는 아이들을 최소화하기 위해서는 고정시키는 아이들을 최대한 많이 선택해야 한다. 즉, 그나마 번호 순서대로 선 아이들의 배열 중 가장 긴 배열을 찾아야 한다는 의미이다. 이 를 찾는 문제는 LIS(Longest Increasing Subsequence) 문제이므로, 따라서 이 문제는 아이들의 배열에 대해 LIS를 찾는 문제라고 할 수 있다.

LIS를 찾기 위해서는 모든 entry가 1인 배열 dp를 만들고 각 아이 i의 앞에 있는 모든 아이들에 대해 만약 앞에 있는 아이 j의 번호가 더 작다면, 앞에 있는 아이의 번호가 그 번호까지의 LIS의 마지막 수일 때 LIS의 길이에 1을 더한 값, 즉 dp[j] + 1과 dp[i] 중 더 큰 값을 dp[i]의 값으로 한다. 이를 마지막 아이까지 반복한다.

여기서 주의할 점은 dp[N-1](0번째 index부터 시작하므로 마지막 아이는 N-1번째이다.)은 N-1번째 아이를 포함하는 LIS의 길이를 저장하고 있으나, 우리가 원하는 것은 아이들의 배열 자체에서의 LIS의 길이이므로 반드시 N-1번째 아이를 포함하고 있을 필요는 없다. 따라서 dp의 최댓값을 구해야 LIS의 길이를 구할 수 있다.

다만, 이 문제는 LIS에 속하는 아이들을 제외한 나머지 아이들을 이동시켜야 하고, 이 아이들의 수의 최솟값을 구하고 있으므로 N에서 LIS의 길이를 빼 준 결과가 최종 결과가 된다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
children = []
for _ in range(N):
    child = int(input())
    children.append(child)
# 초기값으로는 1을 부여하는데, 이는 각 아이 자체가 길이가 1인 수열을 이룰 수 있기 때문이다.
dp = [1 for _ in range(N)]
for i in range(1, N):
    # i번째 아이 앞의 모든 아이를 조사한다.
    for j in range(i):
        # j번째 아이의 번호보다 i번째 아이의 번호가 클 때 증가하는 수열을 만들 수 있다.
        if children[j] < children[i]:
            dp[i] = max(dp[i], dp[j] + 1)
# 궁극적으로 구하고자 하는 것은 LIS에 속한 아이들을 제외한, 이동시켜야 할 아이들의 수이다.
print(N-max(dp))