문제 링크: https://www.acmicpc.net/problem/17383

아이디어만 떠올리면 구현은 어렵지 않은 문제입니다.

풀이

최적화 문제 생각해보기

문제를 처음 보면 각 문제를 어떻게 배치해 풀어야 하는지 고민이 되지만, 문제가 아닌 시간 간격에 초점을 둬봅시다.

tncks0121는 항상 각 문제가 풀리는 시간의 차이에만 신경을 씁니다. 문제를 어떻게 푸는지는 상관 없이, 한 문제를 푼 뒤 다음 문제가 풀리기까지의 시간 간격을 최소한으로 만드는 문제로 해석할 수 있습니다. 이 시간 간격을 $M$이라 합시다.

$M$의 최솟값을 찾는 문제는 최적화 문제입니다. 매개변수 탐색을 활용해 풀 수 있으니, 이제 결정 문제를 생각해 봅시다.

저는 "임의의 시간 간격 $M$에 대해 한 칸의 시간 간격 동안에는 두개의 문제만 풀 수 있을 때, 각 문제별로 풀기 위해 필요한 시간 간격의 총 개수가 $2 \times N$을 넘지 않는가?" 를 결정 문제로 사용했습니다.
문제의 예제 데이터에서 영감을 받았는데, $N$개의 문제를 시간 간격 한 칸당 두 문제씩 배치하려면, $2 \times N$개가 넘어가는 경우는 시간 간격을 더 크게 잡을 수 있는 경우가 존재한다고 생각했습니다. 따라서, $2 \times N$ 이하의 칸을 사용해 모든 문제를 배치할 수 있는 경우를 정답, 그렇지 않은 경우는 오답으로 두고 탐색을 진행했습니다.

이 결정 문제를 통해, 시간 간격 $M$은 NNNNN...NYYYYY 꼴로 나타나며 우리가 필요한 $M$의 최솟값을 결정 문제를 통한 이분 탐색, 즉 매개변수 탐색으로 찾을 수 있습니다.

전체 코드

input = open(0).readline

N = int(input())
times = list(map(int, input().split()))

# 매개변수 탐색의 시작 범위로 사용하기 위한 최대/최소 시간 찾기
min_time = 100000
max_time = 1

for t in times:
    min_time = min(min_time, t)
    max_time = max(max_time, t)

# 매개변수 탐색
left = min_time
right = max_time

while left <= right:
    mid = (left + right) // 2

    # 결정 문제 풀기
    required_time_sectors = 0
    for t in times:
        required_time_sectors += (t + mid - 1) // mid  # ceil(t / mid)

    # 이분탐색 범위 조정
    if required_time_sectors < 2 * N: # N
        right = mid - 1
    else: # N
        left = mid + 1

print(left)

시행착오

이분 탐색의 범위 설정 문제

앞서 결정 문제로 "임의의 시간 간격 $M$에 대해 한 칸의 시간 간격 동안에는 2개의 문제만 풀 수 있을 때, 각 문제별로 풀기 위해 필요한 시간 간격의 총 개수가 $2 \times N$을 넘지 않는가?"를 사용했다고 설명했습니다. 그 말 그대로, $2 \times N$ 이하일 때를 정답으로 보고 범위를 조정할 시 일부 입력에서 오답이 나오는 점을 확인했습니다.

따라서, 결정 문제를 "임의의 시간 간격 $M$에 대해 한 칸의 시간 간격 동안에는 2개의 문제만 풀 수 있을 때, 각 문제별로 풀기 위해 필요한 시간 간격의 총 개수가 $2 \times N$을 작은가?" ($< 2 \times N$)로 변경해 정답을 받았습니다.

while left <= right:
    mid = (left + right) // 2
    required_time_sectors = 0
    for t in times:
        required_time_sectors += (t + mid - 1) // mid  # ceil(t / mid)
    if required_time_sectors <= 2 * N: # 결정 문제의 답이 Y
        right = mid - 1
    else:
        # 결정 문제의 답이 N
        # 찾고자 하는 답은 [mid + 1, end]에 있다.
        left = mid + 1

print(left)