[백준] 2565 전깃줄 (Python 파이썬)

문제 설명

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

2565번: 전깃줄

자세한 문제 설명은 위 링크를 참고하시길 바랍니다.

---

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 최대 증가 수열을 찾는 문제라고 할 수 있다.

 

출처 : 백준 알고리즘

전깃줄이 교차하지 않도록 하려면 어떻게 해야할지에 대해 먼저 생각해보자.

먼저, 위 그림에서 A의 1번과 B의 8번만 연결되어 있다고 가정해보자.

 

그리고 이 때, 아래의 ①번 상황과 ②번 상황을 각각 생각해보자.

 

① A의 2번과 B의 2번이 연결된다면 교차하게 된다. ( 1 - 8 / 2 - 2 )

② A의 3번과 B의 9번이 연결된다면 서로 교차하지 않는다. ( 1 - 8 / 3 - 9 )

 

위의 예시를 보면 다음과 같음을 알 수 있다.

 

전깃줄 두 개가 있을 때, A의 번호가 작은 순서대로 정렬을 하여 첫 번째, 두 번째 전깃줄이라고 순서를 매긴다면

두 번째 전깃줄의 B번호가 첫 번째 전깃줄의 B번호보다 작다면 교차하게 된다.

 

하지만 두 번째 전깃줄의 B번호가 첫 번째 전깃줄의 B번호보다 크거나 같으면 교차하지 않게 된다.

 

이를 그대로 연장하여 전깃줄 세개인 상황을 만들면

세 번째 전깃줄의 B번호가 앞의 두개의 전깃줄의 B번호보다 작다면 교차함을 알 수 있다.

 

즉, 우리가 원하는 그림은 다음과 같음을 알 수 있다.

이런 그림이 탄생하면 전깃줄이 서로 교차하지 않게 된다.

 

그래서 먼저,

① A의 번호가 작은 순서대로 정렬을 하고

② 앞순서의 B가 뒷순서의 B보다 작은 경우가 최대로 이어지는 경우를 찾는다.

 

이렇게 접근을 하기 위해 DP를 이용하면 된다.

앞순서의 B가 뒷순서의 B보다 작은 경우에만 DP 카운팅을 늘려서

최종적으로 최대의 DP카운트를 찾으면 정답을 찾게 된다.

 

이 때, 최대 연장부분을 찾기 위해서는 앞에서부터 하나씩 검사를 해야 하기 때문에

2중 for문을 이용해 DP를 갱신하였다.

 

이를 반영한 파이썬 코드는 다음과 같다.

n = int(input())
lists = []
dp = [1]*n

for i in range(n):
  a, b = map(int, input().split())
  lists.append([a, b])

lists.sort()

for i in range(1, n):
  for j in range(0, i):
    if lists[j][1] < lists[i][1]:
      dp[i] = max(dp[i], dp[j]+1)
      
print(n-max(dp))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !