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

Problem

https://www.acmicpc.net/problem/2869

Solution

오답 코드 (시간초과)

a,b,v = map(int, input().split())

day = 1
snail_height = 0
while 1:
    snail_height+=a
    if v <= snail_height:
        break
    snail_height-=b
    day+=1

print(day)

이 코드는 1일차부터 하루씩 늘려나가면서 찾는 방법인데, 낮은 숫자가 입력되었을 때는 정상 출력되지만 day의 값이 크게 증가하게 되면 찾는 시간이 너무 오래걸리게 된다.

정답 코드

from math import ceil

a, b, v = map(int, input().split())
day = ceil((v-b) / (a-b)) # 실수를 ceil함수를 사용하여 올림
print(day)

Memo

위에는 시간초과가 나지 않는 코드이다. 수식의 의미는 낮에 a만큼 올라가고 밤에 b만큼 올라온다는 의미의 식인 v = a * day + (-b) * (day-1)를 좌변에 day만 남기고 정리한 것이다. 값을 올림한 이유는 day의 값이 소수형태로 나온다는 의미는 하루가 더 필요한 것이기 때문이다.

Ref.

https://stultus.tistory.com/entry/Python-백준-2869-달팽이는-올라가고-싶다
https://yoonsang-it.tistory.com/9