[백준] 2565번 : 전깃줄 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2565번: 전깃줄

 

1. 문제 설명

2. 풀이과정

해당 문제는 전깃줄이 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다.

전깃줄은 A 전봇대에서 B 전봇대로 연결되기 때문에 교차하지 않으려면 연결된 전깃줄을 전깃줄의 B 전봇대 번호를 기준으로 오름차순 정렬하고, 이후 전깃줄을 차례대로 이전 전깃줄과 비교하여 교차되는지 안되는지 확인하면 된다.

처음부터 비교할 전깃줄 전까지 비교하며 만약 이전 전깃줄의 B 전봇대 번호가 더 작으면 해당 두 전깃줄은 서로 공존할 수 있다.

하여 이전 전깃줄의 경우에 1을 더한 결과와 해당 전깃줄의 경우를 비교하여 더 큰 값을 해당 전깃줄에 가능한 경우의 수로 저장한다.

마지막 전깃줄까지 비교를 마치면 가능한 경우의 수 중 최댓값을 전체 전깃줄의 개수에서 빼, 최소 제거 개수를 구한다.

(가장 긴 증가하는 부분 수열을 구하는 문제와 유사하게 해결)

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전깃줄 개수를 입력받는다. N = int(sys.stdin.readline())
3. 전깃줄 연결 정보를 저장할 리스트를 생성한다. li = list()
4. 전깃줄 개수만큼 반복하며 for i in range(N)
5. 연결된 전봇대 번호를 입력받아 리스트로 추가한다. li.append(list(map(int, sys.stdin.readline().split())))
6. 전깃줄의 정보를 연결된 B 전봇대의 번호를 기준으로 정렬한다. li.sort(key=lambda x : x[1])
7. 각 전깃줄 별로 최대 가능한 경우의 수를 저장할 리스트를 생성한다. dp = list(1 for _ in range(N))
8. 두 번째 전깃줄부터 마지막 전깃줄 전까지 비교 대상으로 지정하고 for i in range(1, N)
9. 처음부터 해당 전깃줄 전까지 비교하는 전깃줄을 불러와 for j in range(i)
10. 만약 비교 대상인 전깃줄의 A 전봇대의 번호가 비교하는 전깃줄의 A 전봇대의 번호보다 작으면 if (li[j][0] < li[i][0])
11. 해당 위치의 전깃줄의 가능한 경우를 비교 대상인 전깃줄에 1을 더한 결과와 비교하는 전깃줄의 경우 중 더 큰 값으로 저장한다. dp[i] = max(dp[j] + 1, dp[i])
12. 전체 전깃줄의 개수에서 가장 많은 경우를 빼면 최소로 제거해야 할 전깃줄의 개수를 구할 수 있다. print(N - max(dp))

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

li = list()
for i in range(N):
    li.append(list(map(int, sys.stdin.readline().split())))

li.sort(key=lambda x : x[1])

dp = list(1 for _ in range(N))
for i in range(1, N):
    for j in range(i):
        if (li[j][0] < li[i][0]):
            dp[i] = max(dp[j] + 1, dp[i])

print(N - max(dp))