백준 :: 7570번 줄 세우기 (Python)

문제 링크

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

7570번: 줄 세우기

접근 방식

정렬을 하려고 삽질을 하다가 결국 다른 분들의 풀이를 참조했던 문제 ..

제일 앞이나 제일 뒤로 보내는 어린이의 수를 구하기 위해서는 현재 어린이들 중에서

잘 서 있는 어린이의 수와, 잘못 서있는 어린이의 수를 구하면 된다.

예를 들어 예제 입력으로 나온 5 2 4 1 3 의 경우 2번과 3번은 “잘 서 있다” 라고 말할 수 있다.

그 외의 5, 4, 1번의 어린이는 제일 앞이나 뒤로 이동해서 위치를 바꾸어야 한다.

여기서 LIS (Longest Increasing Subsequence) 를 알고 있다면 풀이에 빠르게 접근할 수 있는데,

이 문제에서는 연속된 수를 가진 가장 긴 증가수열을 찾으면 된다.

다른 예시로 4 2 1 3 5 라는 순서가 있다면, [2, 3] 이 가장 긴 연속된 증가수열이 되고

나머지 4, 1, 5 는 움직여야 한다는 것을 알 수 있다.

이제 코드를 작성해보았는데, n 의 수가 100만이기 때문에 이중 loop 로는 시간초과가 난다.

각 번호의 위치를 배열 인덱스로 활용하면 O(N^2)는 피할 수 있다.

풀이 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
children = list(map(int, input().split(' ')))
idx = [0 for _ in range(N + 1)]

for i, v in enumerate(children):
    idx[v] = i

maxval = 0
cnt = 1
for num in range(1, N):
    if idx[num] < idx[num + 1]:
        cnt += 1
    else:
        maxval = max(maxval, cnt)
        cnt = 1

print(N - maxval if N != 1 else 0)

이후 DP 를 이용해서 코드를 다시 짜보았다.

결국 주어진 수들에서 “가장 길게 증가하는, 연속된 부분 수열” 을 구하는 게 중요한데,

각 수마다 하나 앞의 수가 이미 등장했는지를 확인하면서 기록해나간다는 컨셉이 중요하다.

예를 들어 현재 숫자가 2이면, 1이 이전에 나왔는지를 체크하는 방식 !

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
children = list(map(int, input().split(' ')))

dp = [0 for _ in range(N+1)]
for child in children:
    dp[child] = dp[child - 1] + 1

print(N - max(dp) if N != 1 else 0)

삽질의 흔적.. 확실히 DP를 이용하고 나니까 시간이 절반으로 줄었다.

끝.