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

minidoo·2020년 12월 6일
0

알고리즘

목록 보기
74/85
post-thumbnail
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증가수열
188
222
39(2, 9) (8, 9)
41(2, 9) (8, 9)
64(2, 9) (8, 9) (2, 4) (1, 4)
76(2, 9) (8, 9), (2, 4, 6), (1, 4, 6)
97(2, 9) (8, 9) ... (2, 4, 6, 7)
1010(2, 9) (8, 9)... (2, 4, 6, 7, 10) (1, 4, 6, 7, 10)

0개의 댓글