백준 - 전깃줄(2565)

문제 링크 ▶︎ 백준 전깃줄 2565

문제 전략

이 문제는 DP 문제이다.

전깃줄 data를 2차원 배열로 받은 뒤, 2차원 배열의 첫번째 인덱스를 기준으로 정렬한다.
n 만큼 반복문을 돌면서 {지금 전깃줄} 과 {전의 전깃줄들} 을 비교한다.
그 전까지의 전깃줄들을 검사하면서 겹치지 않는 전깃줄의 수를 dp 리스트에 저장한다.

i 번째 전깃줄의 dp 값(겹치지 않는 전깃줄)은 0 ~ i-1 까지의 전깃줄을 검사하면서 dp값에 +1 한 값을 max 비교하여 넣어주면 된다.

코드

import sys
input = sys.stdin.readline
n = int(input())
lines = []
for _ in range(n):
    lines.append(list(map(int,input().split())))

lines.sort(key= lambda x:x[0])
dp = [1] * n
for i in range(n):
    for j in range(i):
        if lines[i][1] > lines[j][1]:
            dp[i] = max(dp[i],dp[j]+1)

print(n-max(dp))

개선 사항

dp 문제 아이디어는 아직 좀 더 연습을 많이 해봐야할듯.