백준 2565 전깃줄

전깃줄 (백준 2565)

https://www.acmicpc.net/problem/2565

dp 문제로 분류가 되어있었으나,
대체 어떻게 ‘최적부분구조’를 적용할 수 있는지 알 수 없어서
블로그를 본 후, 아이디어를 찾았다

요점은 A번째 전봇대를 기준으로 정렬한 후,
B번째 전봇대의 수에 LIS(최장 부분 증가 수열) 알고리즘을 적용하는 방식이었다

해당 알고리즘이 적용되는 방식은
정렬 후 B 전봇대의,
I번째 수 이후 다음에 존재하는 수가
I번째의 수보다 크다면,
‘전봇대가’ 걸리지 않는다는 점이었다
(이미 A번째로 정렬을 하였기에, 존재하지 않는 경우의 수를 고려할 필요가 없어짐)
따라서 ‘서로 걸리지 않는 가장 많은 전깃줄 수’를 LIS 공식으로 구한 후,
전체 수(num)에서 빼줌으로서
‘최소의 겹쳐서 제거하는 전깃줄 수’를 구할 수 있다

Code

import sys
inp = sys.stdin.readline

num = int(inp().strip())

values = [list(map(int,inp().split())) for i in range(num)]
dp = [1 for i in range(num)]

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

for i in range(num):
    for j in range(i,-1,-1):
        if values[i][1] > values[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(num - max(dp))

해결 아이디어

1. dp[i] : 전봇대 B에서 i번째에서 이전까지 서로 겹치지 않는 전깃줄 수
   
2. 받은 전깃줄 들을 A 전봇대 기준으로 정렬하기
   
3. 이후 B를 기준으로 LIS를 적용
   
4. 해당 수치 중 가장 큰 값으로 num을 빼주기