[백준 2631번] - 줄세우기

그동안 그래프 문제만 풀어대서 문제해결력 향상 + 코드포스 준비를 위해 다이나믹 프로그래밍과 그리디, 수학 위주로 문제를 풀고 있습니다. 너무 안해서 그런지 쉬운것부터 시작하는데도 빌빌거리네요. 마치 1년전 그래프로 빌빌거렸던 시절과 똑같은거 같습니다. 예나 지금이나 실력이 늘지 않는군요 ㅠㅠ

 

2631번: 줄세우기

1부터 N까지 번호가 랜덤하게 나열되어 있습니다. 이 번호들을 오름차순으로 나열할 때, 이동되는 번호들의 최소 갯수를 구하는 문제 입니다.

그러니까 어느 번호가 옮겨지는 지, 어느 위치로 옮겨지는지 그런거 말고 그냥 최소 이동 횟수를 구하기만 하면 됩니다. 

이동 횟수의 최솟값을 구하는 방법은 요소의 갯수 N에서 오름차순으로 나열되어 있는 수열의 부분 집합 중에서 가장 큰 부분 집합의 갯수를 빼면 됩니다. 즉 가장 긴 부분 수열(LIS)의 갯수를 구하는 문제가 되겠습니다.

그 이유는 문제의 목표가 오름차순으로 정렬 입니다. 그렇기 때문에 알아서 증가하는 부분 수열들은 알아서 오름차순으로 정렬되어 있기 때문에 얘들은 건들 필요가 없고 그 나머지 부분만 옮기면 됩니다. 무슨 말인지 모르겠다고요? 저도 몰라여 ㅋㅋ 이게 무슨 개소리인지 예시를 통해 알아봅시다.

 

예시를 보면

3 7 5 2 6 1 4

이렇게 나열되어 있습니다. 여기서 LIS를 구하면 [3, 5, 6] 이 됩니다.

3 7 5 2 6 1 4

그러면 나머지 요소는7, 2, 1, 4가 됩니다. 여기서 순차적으로 오름차순에 맞게 옮겨 봅시다.

우선 7은 가장 큰 수이므로 맨 끝으로 옮깁니다.

3 5 2 6 1 4 7

2는 3 앞으로 옮깁니다.

2 3 5 6 1 4 7

1이 가장 작기 때문에 맨 앞으로 옮깁니다.

1 2 3 5 6 4 7

마지막으로 4를 3의 뒤로 옮기면 완성이 됩니다.

1 2 3 4 5 6 7

따라서 총 4번 옮겼고 이는 요소의 갯수에서 LIS의 갯수를 뺀 값과 같습니다. (7 - 3 = 4)

 

코드 보기

O(n^2)

import sys

input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [0] * N

for i in range(N):
    m = 0
    for j in range(i-1, -1, -1):
        if A[i] > A[j]:
            m = max(m, dp[j])
    dp[i] = m + 1
print(N - max(dp))

O(nlogn)

import sys

input = sys.stdin.readline

def lower_found(a, v):
    n = len(a)
    l, r = 0, n-1
    while l < r:
        m = (l + r) >> 1
        if v <= a[m]:
            r = m
        else:
            l = m + 1
    return r


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

for v in A:
    if not S or S[-1] < v:
        S.append(v)
    else:
        S[lower_found(S, v)] = v
print(N - len(S))

LIS의 기본 문제라고는 하지만 말이 기본문제지 솔직히 여기까지 생각하는데 시간이 엄청 많이 걸렸습니다. 그동안 LIS관련된 문제를 풀어보지 않아서 그런것 같군요. 한참 멀었습니다. DP 풀이를 제대로 할 때 까지 계속 연습해야겠군요 ㅠㅠ