[알고리즘] 동적 계획법(Dynamic Programming) - 백준 2565번 전깃줄

import sys
input = sys.stdin.readline

N = int(input().rstrip())
wire = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
dp = [1] * N

wire.sort(key=lambda x:x[0])

for i in range(N):
    for j in range(i):
        if wire[i][1] > wire[j][1]:
            dp[i] = max(dp[i], dp[j]+1)

print(N-max(dp))

풀이과정

LIS(최장 증가수열)을 이용하는 문제

1. 전봇대A와 전봇대B를 이차원 배열의 형태로 wire에 넣는다.
2. 전봇대A를 기준으로 정렬한다.
3. 만약 전봇대A의 1번이 B의 8번 전깃줄을 선택했다면, 그 아래 전깃줄은 B의 9번 이상의 값과 연결되어야 겹치지 않는다.
4. 위의 설명을 바탕으로 최장 증가수열을 구한다.
5. 정렬된 값을 기준으로 최장 증가수열은 [2, 4, 6, 7, 10] 또는 [1, 4, 6, 7, 10] 이 나온다. 연결할 수 있는 값들이다.
6. 따라서 전체 전깃줄에서 최장 증가수열 길이를 빼면 답을 구할 수 있다.

전봇대A	전봇대B	증가수열
1	8	8
2	2	2
3	9	(2, 9) (8, 9)
4	1	(2, 9) (8, 9)
6	4	(2, 9) (8, 9) (2, 4) (1, 4)
7	6	(2, 9) (8, 9), (2, 4, 6), (1, 4, 6)
9	7	(2, 9) (8, 9) ... (2, 4, 6, 7)
10	10	(2, 9) (8, 9)... (2, 4, 6, 7, 10) (1, 4, 6, 7, 10)