• 출처 : https://www.acmicpc.net/problem/3020

• 알고리즘 : 이분탐색

• 풀이

  1. 바닥의 장애물은 그대로, 천장의 장애물은 (높이-길이)로 입력받는다
  2. 가능한 모든 높이에 대해 개똥벌레가 만나게 되는 장애물 개수를 계산한다
  3. 최댓값과 최댓값의 개수를 구한다

• 장애물 개수 계산법

  1. 계산하려는 높이 리스트를 정렬한다
  2. 이분 탐색을 통해 계산하려고 하는 현재 높이 h와 처음 만나는 경계를 구한다
  3. (높이 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)