[백준] 3020번 개똥 벌레
-
알고리즘 : 이분탐색
-
풀이
- 바닥의 장애물은 그대로, 천장의 장애물은 (높이-길이)로 입력받는다
- 가능한 모든 높이에 대해 개똥벌레가 만나게 되는 장애물 개수를 계산한다
- 최댓값과 최댓값의 개수를 구한다
-
장애물 개수 계산법
- 계산하려는 높이 리스트를 정렬한다
- 이분 탐색을 통해 계산하려고 하는 현재 높이 h와 처음 만나는 경계를 구한다
- (높이 h에 만나는 장애물 개수 x개, 만나지 않는 장애물 개수 - x개)
코드
import sys
def binary_search(length_list, curr_height, start, end):
if start > end:
return start
mid = (start+end)//2
if length_list[mid] < curr_height:
return binary_search(length_list, curr_height, mid+1, end)
else:
return binary_search(length_list, curr_height, start, mid-1)
def init():
rock_num, height = map(int, sys.stdin.readline().rstrip().split(' '))
top_list, bottom_list = [], []
for i in range(rock_num):
if i % 2 == 0:
bottom_list.append(int(sys.stdin.readline().rstrip()))
elif i % 2 == 1:
top_list.append(height-int(sys.stdin.readline().rstrip()))
return rock_num, height, top_list, bottom_list, float('inf'), 0
rock_num, height, top_list, bottom_list, min_num, min_count = init()
bottom_list.sort()
top_list.sort()
for h in range(height):
bottom_meet = rock_num//2 - binary_search(bottom_list, h+0.5, 0, rock_num//2-1)
top_meet = binary_search(top_list, h+0.5, 0, rock_num//2-1)
if min_num == bottom_meet+top_meet:
min_count += 1
elif min_num > bottom_meet+top_meet:
min_num = bottom_meet+top_meet
min_count = 1
print(min_num, min_count)
Author And Source
이 문제에 관하여([백준] 3020번 개똥 벌레), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-3020번-개똥-벌레
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
def binary_search(length_list, curr_height, start, end):
if start > end:
return start
mid = (start+end)//2
if length_list[mid] < curr_height:
return binary_search(length_list, curr_height, mid+1, end)
else:
return binary_search(length_list, curr_height, start, mid-1)
def init():
rock_num, height = map(int, sys.stdin.readline().rstrip().split(' '))
top_list, bottom_list = [], []
for i in range(rock_num):
if i % 2 == 0:
bottom_list.append(int(sys.stdin.readline().rstrip()))
elif i % 2 == 1:
top_list.append(height-int(sys.stdin.readline().rstrip()))
return rock_num, height, top_list, bottom_list, float('inf'), 0
rock_num, height, top_list, bottom_list, min_num, min_count = init()
bottom_list.sort()
top_list.sort()
for h in range(height):
bottom_meet = rock_num//2 - binary_search(bottom_list, h+0.5, 0, rock_num//2-1)
top_meet = binary_search(top_list, h+0.5, 0, rock_num//2-1)
if min_num == bottom_meet+top_meet:
min_count += 1
elif min_num > bottom_meet+top_meet:
min_num = bottom_meet+top_meet
min_count = 1
print(min_num, min_count)
Author And Source
이 문제에 관하여([백준] 3020번 개똥 벌레), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-3020번-개똥-벌레저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)