❓2869번 : 달팽이는 올라가고 싶다.
📈 문제 요약
달팽이가 낮에 A미터 올라갈 수 있고 밤에 B미터 미끄러져 내려올 때 V미터까지 올라가려면 며칠이 걸리는지 구하면 되는 문제
🤨 접근법
다 올라가는 데 걸리는 일수를 D라고 할 때 처음으로 V에 오르게 되는 D를 구하는 최적화 문제이다. 다만 낮에 A미터를 올라가고 밤에 B미터를 내려오므로 최종적으로 올라가는 미터는 A-B 미터가 되겠지만, 낮에 A미터를 올라가는 순간에 V에 오르게 되는 점을 고려해야 한다.
즉, (A-B)*(D-1)+A를 검사해야 하며, 가장 먼저 V를 오르는 D를 찾으면 되며, 결정 문제로 최적화 문제를 해결하는 파라메트릭 서치(매개변수 탐색)으로 풀이할 수 있겠다.
- 결정 문제 : (A-B)*(D-1)+A 가 V를 넘는가?
- 최적화 문제 : 가장 처음으로 V를 넘는 D는?
V를 처음 넘는 D를 찾기 위해 선형탐색으로 1부터 접근한다면 O(N)의 복잡도로, 주어진 수의 범위 (1 ≤ B ≤ A ≤ V ≤ 1,000,000,000)를 고려하면 너무 오랜 시간이 소요될 수 있다.
따라서 이분 탐색으로 log 시간 내에 D를 찾을 수 있도록 하자.
🔡 코드
import sys
input = sys.stdin.readline
def is_goal_during(n):
return ((A-B)*(n-1)+A) >= V
def get_due(low, high):
while low <= high:
mid = (low+high) // 2
if is_goal_during(mid):
high = mid - 1
else:
low = mid + 1
return low
A, B, V = map(int, input().rstrip().split())
print(get_due(1, V))가장 적게 걸리는 일 수 1을 low로 두고, 가장 오래 걸리는 일 수 V를 high로 두어 이들의 중간값인 mid일 수 동안 올랐을 때 V보다 많이 오르는지 검사(is_goal_during(n))한다. 더 많이 올랐다면 high를 mid-1로 낮춰서 다시 중간을 검사해보고, 더 적게 올랐다면 low를 mid+1로 높여서 다시 중간을 검사해보는 과정을 low가 high를 역전할 때까지 반복한다. 역전하게 되는 순간에 low에는 가장 먼저 V를 넘는 일 수 가 담기게 된다.
📚 고찰
파라메트릭 서치 유형의 문제들을 풀이하면서 정확히 같은 이분탐색 코드를 구성해서 파라메트릭 서치를 진행하더라도 어떨 때는 high를, 또 어떨 때는 low를 반환하는 것이 정답인 헷갈리는 상황이 발생했다. 잘 생각해보니 이것은 문제에서 요구하는 바에 따라 달라진다.
랜선 자르기 문제에서는 K개의 랜선으로 동일한 길이의 N개의 랜선을 만들 때 최대 랜선의 길이를 구해야 했는데, 조건을 만족하는 ‘최대’ 값을 찾는 최적화 문제였기 때문에 이분 탐색 로직에서 결정 문제를 만족(만들어지는 랜선이 N개 이상)하게 되면 low를 mid+1로 높여서 결정문제를 만족하지 않는 또 다른 길이를 찾는 방식으로 최적화를 진행한다. 이 경우에는 최종적으로 low가 high를 역전하면 high에 정답이 담겨있다.
반면 이 문제는 V를 오르게 되는 ‘최소’ 일 수를 찾는 최적화 문제기 때문에 결정 문제를 만족(V 이상을 오름)하게 되면 high를 mid-1로 낮춰서 결정 문제를 만족하지 않는 또 다른 일 수를 찾는 방식으로 최적화를 진행한다. 이 경우에는 최종적으로 low가 high를 역전하면 low에 담겨있다.
결국 나는 최대값을 찾는 최적화 문제에서는 high를 반환하도록, 최소값을 찾는 최적화 문제에서는 low를 반환하도록 로직을 구성하고 있다. 이제 헷갈리지 않도록 일관성 있게 코드를 구현하자.
