반응형
https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
위와 같은 상황에서 전깃줄이 겹치지 않도록 할 때, 제거해야 할 전깃줄의 최소 개수를 구해야 한다.
전깃줄이 겹치면 안되므로 증가함수의 형태를 띄어야 하고, 그 중 가장 길이가 긴 부분 배열의 길이를 구해서 전체 배열의 길이에서 빼면 해결된다.
따라서 Binary Searh를 활용한 LIS 알고리즘으로 문제를 해결한다.
import sys
input = sys.stdin.readline
n = int(input())
arr = sorted([list(map(int, input().split())) for _ in range(n)])
# Binary Search 후 값이 들어갈 idx 반환
def BS(arr, s, e, n):
while s < e:
m = (s + e) // 2
if n > arr[m]:
s = m + 1
else:
e = m
return e
# 다음 항목이 부분 배열의 마지막 항목보다 크다면 끝에 붙이고,
# 작다면 적절한 위치를 BS를 통해 구하여 해당 위치에 삽입한다. <- 최대 길이 유지 가능
def LIS(arr, l):
li = []
max_len = 0
for i in range(l):
if i == 0:
li.append(arr[i][1])
max_len = 1
else:
if arr[i][1] > li[-1]:
li.append(arr[i][1])
max_len = max(max_len, len(li))
elif arr[i][1] < li[-1]:
idx = BS(li, 0, len(li), arr[i][1])
li[idx] = arr[i][1]
return max_len
ans = LIS(arr, n)
print(n - ans)
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[Python] 백준 10026번 적록색약 (0) | 2024.01.20 |
---|---|
[Python] 백준 2178번 미로 탐색 (0) | 2024.01.16 |
[Python] 백준 15686번 치킨배달 (0) | 2024.01.16 |
[Python] 백준 7569번 토마토 (1) | 2024.01.15 |
[Python] 백준 11729번 하노이 탑 이동 순서 (0) | 2024.01.13 |