[Python] 줄 세우기 (백준 7570번)

🤔 문제

 

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

 

---

 

🔍 문제 풀이 과정

N=100만이고, N log N ~ 2000만이므로 O(NlogN) 시간 내에 풀어야 하는 문제입니다.

 

처음 봤을 때 떠오른 방식은 최장 증가 부분수열(LIS) 이었습니다.

 

(처음 풀이 코드 - 실패)

import sys

input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))


# target 보다 작은 값 중 가장 큰 값의 index 반환
def binary_search(array, target):
    start, end = 0, len(array) - 1
    result = -1
    while start <= end:
        mid = (start + end) // 2
        if array[mid] < target:
            result = mid
            start = mid + 1
        else:
            end = mid - 1
    return result


# 가장 긴 증가하는 부분 수열(LIS)의 길이를 반환하는 함수
def LIS(array):
    dp = [0]
    for i in range(len(data)):
        idx = binary_search(dp, data[i]) + 1
        if idx >= len(dp):
            dp.append(data[i])
        else:
            dp[idx] = min(dp[idx], data[i])
    return len(dp) - 1


print(n - LIS(data))

 

처음에는 최장 증가 부분수열의 길이를 구하고, 그 길이를 뺀 만큼 이동하면 되겠다는 생각으로 풀었는데 틀렸습니다.

 

직접 반례를 찾아보며 확인한 결과, 일반적인 LIS 를 제외한 숫자만큼 이동하는 것이 틀리다는 것을 확인했습니다.

 

예시를 보면

7
1 4 3 5 2 7 6
// 에서는 LIS가
1 3 5 7
// 이지만, 실제 이동 횟수는 7-4=3 이 아닌 4
4 5 6
// 을 제외한 나머지가 이동하는 횟수 4가 정답

즉, 가장 긴 연속 부분수열을 찾아야 했습니다.

 

증가하는 것보다 연속하는 조건은 더 고려할 점이 적기 때문에, 기존의 LIS 알고리즘 대신 1차원 DP 테이블을 이용해서도 풀 수 있을 것 같아 아래와 같이 풀었습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(n):
    idx = data[i]
    dp[idx] = dp[idx - 1] + 1

print(n - max(dp))

 

dp[i]의 값은 i가 마지막 값인 가장 긴 연속 부분수열의 길이입니다.

 

---

 

📜 결과

 

 

코드는 짧게 나왔지만, 아이디어와 반례를 떠올리기 어려웠던 문제였습니다.