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

Thumbnail: Photo by Jefferson Sees (Unsplash)

최대값 최댓값 어느 쪽이 맞는 표기인지 헷갈려서 찾아봤는데, 최댓값이 맞다고 합니다 ㅎㅎ

풀이

이게 왜 이분 탐색?

~ 한 조건을 만족하는 최대/최솟값을 찾는 형태의 문제들을 최적화 문제 라고 부릅니다. 그러나, 최적화 문제를 왜 이분 탐색으로 풀 수 있는지는 막연히 떠오르지 않을 수 있습니다!

1) 이분 탐색은 무엇인가?

이해에 앞서, 우리가 아는 이분 탐색을 먼저 생각해봅시다. 아래와 같은 배열에서, 임의의 원소 \(K\)가 몇 번 째에 있는지를 찾는 문제를 풀어봅시다.

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

단순히 배열을 순회해서도 찾을 수 있으나, 그렇게 되면 시간 복잡도가 \(O(N)\)이 되며, 대부분의 문제에서 시간 초과를 받게 됩니다.

array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
K = int(input())  # 찾고자 하는 배열 안의 임의의 수
for idx in range(len(array)):
    if array[idx] == K:
        print(idx)

이분 탐색은 최악의 경우에도 \(O(\log N)\)의 시간 복잡도를 가지므로, 배열을 순회하는 방식보다 더 빠르게 답을 찾아낼 수 있습니다.

array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
K = int(input())  # 찾고자 하는 배열 안의 임의의 수

l = 0
r = len(array) - 1
while l <= r:
    m = (l + r) // 2
    if array[m] < K:
        l = m + 1
    elif array[m] > K:
        r = m - 1
    else:
        print(m)

다만, 이분 탐색은 탐색하고자 하는 배열이 정렬되어 있어야 한다는 전제 조건을 가집니다.

2) 결정 문제와 최적화 문제

이분 탐색을 이용해 풀 수 있는 문제 유형 중에, 결정 문제와 최적화 문제가 있습니다.

• 결정 문제: Yes / No로 답할 수 있는 문제
  • ex) 배열 A의 최댓값이 3인가?
• 최적화 문제: 어떤 조건을 만족하는 최댓값/최솟값을 구하는 문제
  • ex) 배열 A의 최댓값을 구하라.

최적화 문제는 결정 문제보다 풀이가 어렵고, 최적화 문제를 풀 수 있다면 그 문제의 결정 문제를 풀 수 있습니다.

3) 최적화 문제의 풀이

최적화 문제는 결정 문제로 바꿔서 풀이할 수 있습니다.

ex) 배열 A의 최댓값을 구하는 문제 (최적화 문제) → 배열 A의 최댓값이 \(K\) 이하인지 판단하는 문제 (결정 문제)

이후, 결정 문제를 \(K = 0, 1, 2, \cdots\) 에 대해 풀면 답을 찾을 수 있습니다.

예를 들어, 배열 A의 최댓값이 10이라 하면, \(K\)에 따라 푼 각각의 결정 문제의 답은 다음과 같습니다.

• \(K = 0\) → No
• \(K = 1\) → No
• ...
• \(K = 10\) → Yes
• \(K = 11\) → Yes
• ...

이를 배열처럼 나타내 보면, NNNNNNNNNYYY.... 꼴입니다.

즉, 배열 A의 최댓값을 구하는 최적화 문제는 결정 문제에서 사용한 임의의 \(K\) 중 결정 문제의 답이 처음으로 Y가 나오는 \(K\)를 찾는 문제로 바꿔 풀 수 있습니다.

정리하면 다음과 같습니다:

• 조건을 만족하는 최댓값을 탐색
  • YYYYYYNNNN... 에서 가장 마지막으로 나오는 Y의 위치를 찾는 문제
  • 정답이 존재하는 구간 \([S, E]\)와 중간값 \(M\)에 대해, 결정 문제 decision(M)의 해가
    • Y라면 정답은 \([M, E]\)에 존재
• N이라면 정답은 \([S, M - 1]\)에 존재
• 이분 탐색 종료 후, \(S\)를 답으로 사용합니다.
• 조건을 만족하는 최솟값을 탐색
  • NNNNNNYYYY... 에서 가장 처음으로 나오는 Y의 위치를 찾는 문제
  • 정답이 존재하는 구간 \([S, E]\)와 중간값 \(M\)에 대해, 결정 문제 decision(M)의 해가
    • Y라면 정답은 \([S, M]\)에 존재
  • N이라면 정답은 \([M + 1, E]\)에 존재
  • 이분 탐색 종료 후, \(E\)를 답으로 사용합니다.

이처럼 '최적화 문제를 결정 문제로 바꾸어 푸는 알고리즘' 을 매개변수 탐색(Parametric Search) 라고 합니다.

문제 분석: 매개변수 탐색

문제에서 구해야 하는 것은 '단독 우승을 하기 위해 부스터를 사용해서 이동해야 하는 최소한의 거리' 입니다. 최솟값을 찾는 매개변수 탐색으로 접근해 풀이할 수 있습니다.

최소한의 거리를 구하기 위한 범위 \([S, E]\)는 \(S = 1, E = Y + 1\)로 설정했습니다.
이후, 이분 탐색이 종료된 뒤의 답(최솟값을 찾는 경우는 \(E\)를 답으로 사용합니다.) 이 \(Y + 1\)이라면, 부스터를 사용해도 단독 우승이 불가능한 경우로 판단하고 -1을 출력합니다.

전처리

결정 문제를 만들기 위해, 먼저 자신을 제외한 나머지 참가자들 중 가장 빠른 사람의 기록이 필요합니다. 이를 fastest_record에 저장하겠습니다.

for _ in range(int(input())):
    N, X, Y = map(int, input().split())
    V = list(map(int, input().split()))

    # 자신을 제외한 참가자들 중 가장 빨리 통과한 선수가 걸린 시간을 계산한다.
    fastest_record = X
    for i in range(N - 1):
        fastest_record = min(fastest_record, X / V[i])

이분 탐색을 하지 않는 경우 예외처리

다음으로, 이분 탐색을 진행하기 전 부스터를 사용하지 않았을 때의 자신의 기록을 계산합니다. 만약 부스터를 사용하지 않아도 이미 단독 우승이 가능한 경우, 즉시 0을 출력하고 다음 케이스로 넘어갑니다.

my_record = X / V[-1]  # 자신의 기록은 항상 마지막에 주어진다.
# 굳이 부스터를 쓰지 않고도 이미 단독 우승이 가능한 경우
if my_record < fastest_record:
    print(0)
    continue

매개변수 탐색(Parametric Search)

이제 '단독 우승을 하기 위해 부스터를 사용해서 이동해야 하는 최소한의 거리'를 매개변수 탐색으로 계산해야 합니다.

앞서 초기 탐색 범위 \([S, E]\)를 \(S = 1, E = Y + 1\)로 설정했습니다. 이제 결정 문제를 사용해 이분 탐색을 진행해야 합니다. 결정 문제는 다음과 같습니다:

처음 1초를 부스터로 \(M\)만큼 이동한 뒤, 자신의 속도 \(V[N - 1]\)로 나머지 거리를 이동하는데 걸린 시간(자신의 기록) 이 fastest_record보다 작은가?

이때, 오로지 '단독 우승'이 가능한 경우만 정답으로 치므로 공동 우승 또한 오답으로 처리해야 합니다. 따라서, 탐색 범위를 다음과 같이 좁혔습니다:

• 거리 \(M\)만큼 부스터를 사용해 걸린 시간 >= fastest_record
  • 오답인 경우이므로, 다음 탐색 구간을 \([M + 1, E]\)로 한다.
• 그렇지 않다면
  • 정답인 경우이므로, 다음 탐색 구간을 \([S, M]\)으로 한다.

이분 탐색이 종료된 후, \(E\)에 해당하는 값을 정답으로 사용한다. 이때, \(E\)가 \(Y\)보다 크다면(\(Y + 1\)이 된다.), 부스터를 써도 단독 우승이 불가능한 경우이므로 -1을 출력해준다.

l = 1
r = Y + 1
while l < r:
    mid = (l + r) // 2
    # 부스터를 사용했을 때, 최소 시간 계산 (결정 문제)
    total_time = (X - mid) / V[-1] + 1 # 최초 1초는 부스터 사용
    if total_time >= fastest_record: # 공동 우승까지는 원하지 않는 경우이므로, 같은 시간이 걸리는 경우는 N으로 처리
        l = mid + 1
    else:
        r = mid
if l > Y:
    print(-1)
else:
    print(r)

전체 코드

input = open(0).readline

for _ in range(int(input())):
    N, X, Y = map(int, input().split())
    V = list(map(int, input().split()))
    fastest_record = X
    for i in range(N - 1):
        fastest_record = min(fastest_record, X / V[i])
    
    if fastest_record > X / V[-1]:
        print(0)
        continue

    l = 1
    r = Y + 1
    while l < r:
        mid = (l + r) // 2
        total_time = (X - mid) / V[-1] + 1
        if total_time >= fastest_record:
            l = mid + 1
        else:
            r = mid
    if l > Y:
        print(-1)
    else:
        print(r)