[백준/Python] - 2565 전깃줄

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

 

 

제출코드

N = int(input())

N_list = []

dp = [0] * (N)

for _ in range(N):

    a, b = map(int, input().split())

    N_list.append([a,b])

N_list = sorted(N_list, key=lambda x:x[0])

for i in range(len(N_list)):

    for j in range(i):

        if N_list[i][1] > N_list[j][1]:

            dp[i] = max(dp[i], dp[j]+1)

print(dp)

print(N - (max(dp)+1))

 

일단 뭐 어떻게 접근하는지도 몰라서 찾아보면서 풀었다.(LIS응용 문제라고 한다.)

풀면서 생각을 해보니 LIS가 맞는거 같기도 하고 ㅎㅎ...

 

핵심 접근법은

일단 N_list에 [a,b]형식으로 a와 b를 매핑시켜준다.

sorted함수를 사용해서 매핑시킨 [a,b]배열을 x[0]즉 a를 기준으로 오름차순 정렬을 해주는데 

여기서 2중 for문으로

i번째의 값(현재 전봇대)과 j번째 값(i번째 전까지의 모든 전봇대)(i-1)까지 비교를 하는데 

i번째 값이 j번째 값보다 크면 → 교차하지 않는 부분수열의 일부가 된다는 소리이다.

해당 조건문이 통과되면 N_list[i]가 교차하지 않는 부분수열의 일부가 될 수 있다는 소리이므로 

N_list[i] 앞에 올 수 있는 모든 이전 유효한 수열(N_list[j])중 가장 긴 교차하지 않는 전봇대에 자기자신(N_list[i])를 추가하여 저장한다.

---

도움이 될지는 모르겠지만 그림도 하나 투척하고 간다ㅎㅎ...

 

---

DP는 너무 어렵다

하지만 공부를 하다가 지칠때는 궤도님처럼 마인드 컨트롤을 해보자