[백준] 2631번 줄세우기 해설 및 풀이 (Python)

 

백준 2631번 줄세우기

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

 

---

문제

 

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

입력

 

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

출력

 

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

 

---

 

 

문제 풀이

 

문제 유형

다이나믹 프로그래밍

 

풀이 도출 과정

 

이 문제를 해결하기 위해서 가장 긴 증가하는 수열 (LIS)를 사용할 것입니다.

 

LIS란?

주어진 배열에서 가장 길게 유지할 수 있는 오름차순 부분 수열입니다.
LIS의 길이를 구하면 최소 이동해야 하는 아이들의 수는 N - LIS 길이가 됩니다.

 

이 문제를 풀기 위해서는 두 가지 방법이 있는데, 다이나믹 프로그래밍(dp) 방법과 이분 탐색이 있습니다.

 

시간 복잡도

 

DP 기반 LIS는 O(N^2)시간이 걸립니다.

이분 탐색을 이용한 LIS는 O(Nlog⁡N)으로 최적화됩니다.

 

---

 

문제 풀이 코드 (DP 기반)

 

N = int(input())
nums = [int(input()) for _ in range(N)]


# DP 배열 초기화
dp = [1] * N


# LIS 구하기
for i in range(N):
    for j in range(i):
        if nums[j] < nums[i]:  # 증가하는 부분 수열
            dp[i] = max(dp[i], dp[j] + 1)


# 최소 이동해야 하는 아이 수 = 전체 개수 - LIS 길이
print(N - max(dp))

 

DP 기반 풀이 코드 설명

 

1. 아이들의 수 N과 1번째부터 N까지의 아이들의 순서 리스트 nums를 입력 받습니다.
2. dp를 통해서 LIS를 구할 것입니다. dp[i] : nums[i]를 마지막 원소로 하는 LIS의 길이를 저장합니다. 모든 dp[i]를 초기값을 1로 설정합니다. LIS는 다음과 같이 for문을 통해 구합니다.

• i번째 숫자를 기준으로 앞의 j(0 ~ i-1)까지 확인합니다.
• nums[j] < nums[i] 이면 dp[j] + 1로 dp[i] 갱신합니다.

3.결과값으로 max(dp)가 LIS의 길이, 즉 최소 이동해야 하는 아이들의 수 = N - LIS 길이입니다. (N - max(dp))

 

 

 

문제 풀이 코드 (이분 탐색 기반 - bisect 라이브러리(이진 탐색) 사용)

 

import bisect

N = int(input())
nums = [int(input()) for _ in range(N)]

# 가장 긴 증가하는 부분 수열 찾기
LIS = []

for num in nums:
    idx = bisect.bisect_left(LIS, num)  # LIS에서 현재 num이 들어갈 위치 찾기
    if idx == len(LIS):
        LIS.append(num)  # 새로운 숫자를 추가
    else:
        LIS[idx] = num  # 기존 자리 대체

# 최소로 옮겨야 하는 아이들의 수 = 전체 개수 - LIS 길이
print(N - len(LIS))

 

이분 탐색 기반 풀이 설명

 

1. 아이들의 수 N과 1번째부터 N까지의 아이들의 순서 리스트 nums를 입력 받습니다.
2. LIS 리스트를 유지하고, nums 리스트에 bisect_left(LIS, num)를 사용해 num이 들어갈 위치(idx)를 찾습니다.

만약 위치(idx)가 LIS의 길이라면 새로운 요소를 추가합니다.

그렇지 않으면 LIS[idx] = num을 통해 값을 갱신합니다.

 

3. 전체 개수에서 LIS 길이를 뺀 값이 최소로 이동하는 아이의 수, 결과값이 됩니다.