백준 - 전깃줄 - 2(2568) 본문
이것도 시리즈 문제인 듯하다.
가장 긴 증가하는 부분 수열의 알고리즘을 이용하면 된다.
dp로 하면 메모리 초과 나서
이분탐색으로 풀어주어야 한다.
제거해야 할 전깃줄 개수는 쉽게 구할 수 있었으나 요소를 구하는데 고민을 많이 했다.
lis 리스트를 하나 만들어서 최장길이 값을 넣어주고
역순으로 탐색을 해서 제거대상을 뽑아 주었다.
def bs_func(target):
l,r = 0,len(bs)
t = 0
while l <= r:
mid = (l+r) // 2
if bs[mid] < target:
l = mid+1
else:
r = mid-1
t = mid
return t
n = int(input())
data = []
for _ in range(n):
data.append(list(map(int, input().split())))
data = sorted(data)
bs = [data[0][1]]
lis = [0]*n
lis[0] = 1
for i in range(1,n):
if bs[-1] < data[i][1]:
bs.append(data[i][1])
lis[i] = len(bs)
else:
idx = bs_func(data[i][1])
lis[i] = idx + 1
bs[idx] = data[i][1]
max_count = n-len(bs)
each_count = n-max_count
answer = []
for i in range(n-1,-1,-1):
if each_count != lis[i]:
answer.append(data[i][0])
else:
each_count -= 1
print(max_count)
for i in sorted(answer):
print(i)
'알고리즘' 카테고리의 다른 글
백준 - 부분수열의 합 2 (1208) (0) | 2023.12.27 |
---|---|
프로그래머스 - 길 찾기 게임 (1) | 2023.12.21 |
백준 - 멀티탭 스케줄링(1700) (0) | 2023.12.12 |
백준 - 가장 긴 증가하는 부분 수열5(14003) (0) | 2023.12.12 |
백준 - 선분 그룹(2162) (0) | 2023.12.12 |
Comments