백준 2631 줄세우기 Python

🐸 문제 정보

2631번: 줄세우기

 

🤖 알고리즘

DP

 

⏱️ 풀이 시간

failed

 

📝 풀이

오랜만에 failed...

문제를 보고 DP라는 것은 알았으나, 도저히 점화식과 아이디어가 떠오르지 않았다.

그리고 결국 검색해서 풀이를 살펴보니 LIS(가장 긴 증가하는 부분수열) 문제라는 것을 깨달았다.

유사한 문제는 이전에도 풀어본 적 있는데, 이 문제가 도대체 왜 LIS 문제지? 라고 생각했으나

이 문제의 입력에서 도출되는 가장 긴 증가하는 부분 수열은 곧 제대로 된 위치에 있는 아이들과 같기 때문에 모든 아이의 수에서 제대로 된 위치에 있는 아이의 수를 빼주면 정답이라는 것을 알게되었다.

 

유사한 문제는 아래에 있다.

11053번: 가장 긴 증가하는 부분 수열

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = [int(input().rstrip()) for _ in range(n)]
dp = [1] * n

for i in range(n):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[j] + 1, dp[i])

print(n - max(dp))