백준 2565 파이썬 - 전깃줄 - 동적 계획법, LIS

백준 2565 파이썬

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

2565번: 전깃줄

이번 문제는 전깃줄이 서로 교차하지 않게 없애야하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 문제를 어떻게 접근해야할지 모르겠다고 생각했는데... 역시 알고리즘은 종이에 적어가면서 경우의 수를 찾다보니 규칙을 찾았습니다. 이 문제도 이전에 풀었던 LIS 문제 :

[CS/알고리즘] - 백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 의 연장선 응용이다.

 

전길줄의 연결 시작점을 기준으로 도착 지점을 적어보면....

{8, 2, 9, 1, 4, 6, 7, 10}

서로 전길 줄이 교차하지 않게 하려면... 연속적으로 증가하는 숫자가 필요하다. 즉, 가장 긴 증가하는 부분 수열의 길이가 최대로 겹치지 않고 연결할 수 있는 전깃 줄이다.

 

Python 풀이

import sys
read = sys.stdin.readline

N = int(read())
lines = [list(map(int, read().split())) for _ in range(N)]
lines.sort(key=lambda x: x[0])
seq = [x[1] for x in lines]

counts = [seq[0]]
for i in range(1, N):
    if counts[-1] < seq[i]:
        counts.append(seq[i])
    else:
        idx = 0
        for j in range(len(counts)):
            if counts[j] < seq[i]:
                idx += 1
            else:
                counts[idx] = seq[i]
                break
print(N - len(counts))

• 증가하는 가장 긴 부분 수열을 구하는 로직은 이전 문제와 똑같다.
• 차이가 있는 부분은 연결되는 선이 출발점의 숫자를 기준으로 오름차순으로 정렬되어야한다.
• 결과는 전체 전깃줄에서 증가하는 가장 긴 부분 수열의 길이를 뺀 값이다.