본문 바로가기
CS/알고리즘

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

by 마이자몽 🌻♚ 2021. 10. 15.

백준 2565 파이썬

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

 

2565번: 전깃줄

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는

www.acmicpc.net

이번 문제는 전깃줄이 서로 교차하지 않게 없애야하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 문제를 어떻게 접근해야할지 모르겠다고 생각했는데... 역시 알고리즘은 종이에 적어가면서 경우의 수를 찾다보니 규칙을 찾았습니다. 이 문제도 이전에 풀었던 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))
  • 증가하는 가장 긴 부분 수열을 구하는 로직은 이전 문제와 똑같다.
  • 차이가 있는 부분은 연결되는 선이 출발점의 숫자를 기준으로 오름차순으로 정렬되어야한다.
  • 결과는 전체 전깃줄에서 증가하는 가장 긴 부분 수열의 길이를 뺀 값이다.

댓글0