[BOJ] 2631 - 줄세우기 (Python)

 

 

아이디어

 

아이들 수에서 최장 증가 부분 수열의 길이를 뺀다.

 

 

풀이

 

리스트 child에 아이들의 번호를 입력 받아 저장하고, 1로 채워진 N 길이의 리스트 dp를 만든다.

이중 for문에서 j번째 아이의 번호가 앞에 있는 i번째 아이 번호보다 크면 증가 부분 수열 길이를 비교해 갱신한다.

마지막에 아이들 수 N에서 최장 증가 부분 수열의 길이를 빼서 출력한다.

 

import sys

N = int(input())
child = list(map(int, sys.stdin.readlines()))
dp = [1]*N
for i in range(N-1):
    for j in range(i+1, N):
        if child[i] < child[j] and dp[j] < dp[i]+1:
            dp[j] = dp[i]+1
print(N-max(dp))

 

 

sys.stdin.readlines로 입력 받는 코드가 내장 함수 input으로 입력 받는 코드보다 더 빨랐다.

# 1.
N = int(input())
child = [int(input()) for _ in range(N)]

# 2. 더 빠른 코드
import sys

N = int(input())
child = list(map(int, sys.stdin.readlines()))