[알고리즘/DP] 2565번 : 전깃줄 - python

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

2565번: 전깃줄

 

---

• 문제
• 소요시간:25분 실패

---

• 설계하기(접근방법) 

1. 입력받기

전깃줄 리스트를 입력받는다

 

2. 구현하기

현재 왼쪽 전깃줄을 기준으로 그 전 전깃줄 중

최대값을 가져오면 될 것 같았는데

어떻게 우측 값을 조절해야하는지

떠올리질 못했다

 

현재 전깃줄을 기준으로

첫 전깃줄 부터 최대값을 비교한다

그 중 현재 전깃줄의 우측 값보다

작은 값들로만 비교한다

 

우측 값이 현재보다 작다면

비교하는 전깃줄의 dp(이전 전깃줄)는

항상 비교하는 전깃줄의 우측값보다

작을 것이기 때문에 최적의 해를 보장할 수 있다.

 

그 중 가장 최대인 값 + 1을 해준다

 

3. 출력하기

전깃줄의 총 개수에서 최대값을 빼주어

즉 삭제해야하는 전깃줄의 개수를 출력한다

 

---

• 코드(출력)

n = int(input())

elec = []

dp = [1] * (n)

for _ in range(n):
    start, end = map(int, input().split())
    elec.append([start, end])

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

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


print(n - max(dp))

---

• 얻어갈 부분

1. 실패했지만 이해하려고 끝가지 노력했다.