백준 / 브론즈 1 / 2869. 달팽이는 올라가고 싶다

• 우와...! 무려 $V$의 최댓값이 1,000,000,000
• 심지어 시간제한이 0.25초다. 이 정도 크기면 $O(N)$으로 풀어도 시간초과 뜸.
• 이걸 $O(1)$으로 풀어요?? 하지만 방법이 있즤~~

풀이

식 세우기

• 달팽이가 $V$미터의 나무 막대를 다 올라갔을 때, $x$일이 걸렸다고 가정. 우리는 $x$의 최솟값을 찾아야 함
• 달팽이는 낮에 $A$미터 올라가고 밤에 $B$미터 떨어짐 -> 하루에 $(A-B)$미터 올라감
• 하지만 마지막 날에는 $A$미터 올라가고 목표에 도달 -> 마지막 날은 $A$미터 올라감
• 즉 달팽이는 $(x-1)$일 간 $(A-B)$미터만큼, 1일 간 $A$미터만큼 올라감
• 올라간 총 높이가 $V$미터 이상이어야 함

정리해서, 아래와 같은 부등식을 세울 수 있음

$(A - B)(x - 1) + A \geq V$ (단, $x$는 자연수)

식 정리하기

$x$를 기준으로 항을 정리하면,

1. $(Ax - Bx - A + B + A) \geq V$

2. $(A - B) x + B \geq V$

3. $(A - B) x \geq (V - B)$

4. $x \geq \frac{(V - B)}{(A - B)}$ ($A > B$이므로 나누어도 부등호는 바뀌지 않음)

즉 $\frac{(V - B)}{(A - B)}$ 이상인 자연수 $x$ 중 최솟값을 구하면 되는데, 해당 값을 올림해 주면 됨 (math.ceil() 사용)

import math

A, B, V = map(int, input().split())

answer = math.ceil((V - B) / (A - B))
print(answer)

시간 복잡도

• 단순 계산이므로 $O(1)$
• 시간제한이 비정상적으로 짧으면 뭔가 신박한 풀이로 풀어야 함

기억할 점

• 달팽이는 해롭다.