99클럽 코테 스터디 31일차 TIL: 부분 수열 DP 심화

오늘의 문제 | 2631. 줄세우기

오늘 문제는 오랜만에 골드가 나왔다. 순서대로 배치하기 위해서 드는 최소 비용을 구하라고 했다. 약간은 그리디적이긴 한데, 아이디어가 이전에 풀었던 알고리즘과 비슷하다는 생각이 든다.

아이디어: 가장 긴 증가하는 부분 수열

우선 우리가 옮기지 않아도 되는 친구들의 수를 최대화시키는 방법을 떠올릴 수 있다. 오름차순으로 정렬하기 위해서, 증가하는 수열을 제외한 나머지만 옮기는건 무조건 이득이라는 것을 알 수 있다. 다만 이게 무조건적으로 최소값인지는 약간은 의문이 들기는 한다.

n=int(input())
l=[int(input()) for i in range(n)]

dp=[1]*(n+1)
for i in range(n-1):
    for j in range(1,i):
        if l[j]<l[i]:
            dp[i]=max(dp[i],dp[j]+1)
print(len(l)-max(dp))

하지만 이렇게 제출했을 때 31%에서 틀렸다고 한다. 뭔가 예외 케이스가 존재하는구나 싶어서 예외를 찾아나서기 시작했다.

n=int(input())
l=[int(input()) for i in range(n)]

dp=[1]*(n+1)
for i in range(n):
    for j in range(i):
        if l[j]<l[i]:
            dp[i]=max(dp[i],dp[j]+1)
print(len(l)-max(dp))

사실 예외는 없었고… 마지막 원소를 검사하지 않아서 생긴 문제였다. 다만 n-1까지 루프를 돌렸을 때도 충분히 답을 맞았던거 같은데 이게 왜 차이가 생기는지 의문이다.

알고보니 예전에도 n까지 반복했었다… 약간 생각을 잘못한 듯하다.

오늘의 회고

골드4 치고는 예전 다른 문제들과 결이 비슷해서 당황했다. 물론 이 문제를 처음 보고 이런 아이디어를 떠올린다는게 쉽지는 않을 거라고 생각하지만 연속으로 계속 비슷한 코드가 나온다는게 아쉽긴 하다.