https://www.acmicpc.net/problem/3020
개똥벌레가 [석순-종유석-석순-..] 순으로 번갈아 등장하는 동굴을 지나갈 때,
최소한의 장애물에 부딪히도록 하는 높이를 찾는 문제다.
귀여운 제목에 이끌려 들어갔다가 큰 코 다친 문제 🐛
처음에 높이를 이분 탐색해야 한다고 잘못 생각해서 오래 걸렸다.
높이는 순차적으로 탐색하고, 석순과 종유석 높이를 각각 이분 탐색해주면 된다. (🔗 참고)
1. 석순과 종유석을 입력 받고, 정렬해준다.
h_arr, l_arr = [], []
for i in range(n):
t = int(input())
if i % 2 == 0:
l_arr.append(t)
else:
h_arr.append(t)
# 석순 l_arr / 종유석 h_arr
l_arr.sort()
h_arr.sort()
2. 높이가 h일때, 부딪히는 장애물의 개수를 체크하는 함수를 만든다.
def check(height, cave):
# 개똥벌레 높이가 height일때
l, r = 0, len(cave) - 1
while l <= r:
mid = (l + r) // 2
if cave[mid] <= height:
l = mid + 1
else:
r = mid - 1
return len(cave) - (r + 1)
[개똥벌레가 높이 height로 날 때 장애물에 부딪히는 경우]
석순
석순의 높이가 height보다 클 때종유석
(동굴 높이-종유석 높이)가 height보다 클 때for i in range(1, h+1):
l_cnt = check(i-1, l_arr)
h_cnt = check(h-i, h_arr)
cur_cnt = l_cnt + h_cnt
height
보다 큰 요소의 개수는 부딪히는 장애물의 개수를 의미한다.
따라서 이분 탐색으로 범위를 줄여나가면서 height
가 들어갈 수 있는 적절한 위치를 찾아줄 것이다.
이분탐색이 끝나고 났을 때 r
은 height
가 삽입될 수 있는 위치를 반환한다.
즉 r+1
는 height
보다 작은 값들의 갯수다.
우리는 height
보다 큰 값의 갯수를 구해야 하므로
부딪히는 장애물의 갯수는 (cave
의 길이 - (r + 1
)) 이다.
3. 가장 작은 장애물에 부딪히도록 하는 높이를 찾는다.
if cur_cnt < answer:
answer = cur_cnt
answer_cnt = 1
elif cur_cnt == answer:
answer_cnt += 1
else:
pass
import sys
input = sys.stdin.readline
def check(height, cave):
l, r = 0, len(cave) - 1
while l <= r:
mid = (l + r) // 2
if cave[mid] <= height:
l = mid + 1
else:
r = mid - 1
return len(cave) - (r + 1)
n, h = map(int, input().rsplit())
h_arr, l_arr = [], []
for i in range(n):
t = int(input())
if i % 2 == 0:
l_arr.append(t)
else:
h_arr.append(t)
l_arr.sort()
h_arr.sort()
answer, answer_cnt = sys.maxsize, 0
# 어쨌든 모든 높이는 순차탐색을 해야함
for i in range(1, h+1):
l_cnt = check(i-1, l_arr)
h_cnt = check(h-i, h_arr)
cur_cnt = l_cnt + h_cnt
if cur_cnt < answer:
answer = cur_cnt
answer_cnt = 1
elif cur_cnt == answer:
answer_cnt += 1
else:
pass
print(answer, answer_cnt)
#input
20 10
5
5
6
4
6
7
9
1
4
4
9
4
9
3
7
1
5
1
6
5
# output
10 9
---
#input
6 5
1
3
4
2
2
3
# output
2 1