백준 2565번 파이썬 문제풀이(전깃줄) - DP(탑다운)

---

후.... 하루종일 뚫어져라봐도 가장 긴 증가 부분수열의 개수를 구하라는 문제인지를 몰랐다.. 골드 5라고 하는데 아마 LIS가 웰노운이라서 골드 5이지 문제만 보고 LIS 알고리즘을 생각하는건 쉽지 않다..... 

어찌됐든 문제의 접근방식은 전봇대 번호를 기준으로 정렬한 후 연결된 번호들을 기준으로 가장 긴 증가하는 부분수열의 개수를 구한 다음 전체의 전봇대 개수에서 빼주면 된다.

 

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

arr.sort(key=lambda x: (x[0]))
arr += [[0, 0]]
dp = [[-1] * (N + 1) for _ in range(N + 1)]


def dfs(cur, pre):
    if cur >= N:
        return 0

    if dp[cur][pre] != -1:
        return dp[cur][pre]

    if arr[cur][1] > arr[pre][1]:
        dp[cur][pre] = max(dfs(cur + 1, cur) + 1, dfs(cur + 1, pre))
    else:
        dp[cur][pre] = dfs(cur + 1, pre)

    return dp[cur][pre]


print(N - dfs(0, -1))