문제 링크
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
문제 풀이
- 이 문제는 '가장 긴 증가하는 부분 수열' 문제로 생각할 수 있다.
- 옮겨지는 아이들의 수가 최소가 되려면 현재 번호대로 줄 서 있는 아이들 수가 최대가 될 때, 그렇지 않은 나머지 아이들이 움직이면 된다.
- 따라서, 전체 아이들 수에서 번호가 증가하는(차례로 있는) 아이들 수를 제외하면 된다.
전체 코드
import sys
input = sys.stdin.readline
n = int(input())
children = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(n):
for j in range(i):
if children[j] < children[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 16234 인구 이동 (0) | 2024.05.12 |
---|---|
[백준/Python] 14719 빗물 (0) | 2024.04.09 |
[백준/Pyhon] 14002 가장 긴 증가하는 부분 수열 4 (0) | 2024.04.04 |
[백준/Python] 14891 톱니바퀴 (0) | 2024.04.03 |
[백준/Python] 14502 연구소 (0) | 2024.03.28 |