[백준] 2869번: 달팽이는 올라가고 싶다(Python)

[2869번] 달팽이는 올라가고 싶다

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

---

실패한 풀이

import sys
input = sys.stdin.readline

A, B, V = map(int, input().strip().split())
day = 0
sum = 0

while True:
    sum += A
    day += 1
    if sum >= V:
        break
    else:
        sum -= B

print(day)

처음에 작성한 코드는 V에 도달할 때까지 반복문이 내부 코드가 계속 실행되는 방식이다. 그래서 반복문 내부의 연산은 O(1)이지만, 반복문이 V/(A-B)번 실행되기 때문에 전체 시간복잡도는 $O({V}/(A-B))$인 것이다.

만약 예제 입출력 3번과 같이, 목표까지 도달하려면 999999901번의 반복이 필요하다. 이렇게 반복 횟수가 수백만 단위로 증가하면 0.25초 안에 처리하지 못해 시간초과가 발생한다.

처음에 풀 때, 예제 입출력 3번이 있는지를 못봐서 이 부분을 고려하지 않고 풀었다.

정답 풀이

import math
import sys
input = sys.stdin.readline

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

# 계산
if A >= V:
    print(1)  # 첫날 바로 도달 가능
else:
    day = math.ceil((V - A) / (A - B)) + 1
    print(day)

수학적인 계산을 통해서 이를 해결할 수 있다.

1. 마지막 날 이전에 필요한 최소 높이는 $V-A$이다.
2. 매일 순수하게 올라가는 높이는 $A-B$이다.
3. 정상까지 도달하기 위한 필요한 날 수를 계산하면 $(V-A)/(A-B)$이다. 여기서 이 값은 올림을 해주어야 한다.
4. 마지막 날에는 A만큼 올라가기 때문에 3번 계산에서 1일을 추가한다.

이렇게 반복문 없이 단순 계산으로 해결하기 때문에 시간 복잡도는 O(1)로 시간 안에 실행할 수 있다.