[Python] Baekjoon2869: 달팽이는 올라가고 싶다

달팽이는 올라가고 싶다

0.15 초 (추가 시간 없음) (하단 참고)

128 MB

127468

34539

29336

28.620%

문제

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

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

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

입력

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

출력

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

풀이

반복문으로 풀이하면 엄청난 시간이 소모됩니다. 다음 테스트 케이스가 대표적인 예입니다

100 99 1000000000

이 때문에 반복문을 사용하는 것이 아닌 수학적인 접근이 필요합니다.

 

아이디어

달팽이는 낮에 올라가고 밤에 미끄러집니다. 꼭대기는 무조건 낮에 도착해야 합니다. 왜냐하면 밤에는 미끄러지기 때문입니다.

즉 낮에 +day 만큼 움직이고 밤에 -night 만큼 움직여서 꼭대기에 도달한다고 하면

꼭대기(height)에 도달한 날인 N째 날의 달팽이의 총 움직인 거리는 다음과 같습니다.

height = N x day + (N - 1) x night # N은 달팽이가 움직인 날의 수

 

N을 구하기

N을 구하기 위해서는 식을 정리해야합니다

height <= N x day + N x night - night

height + night <= N x ( day + night )

(height + night ) / ( day + night ) <= N

여기서 좌항이 만약 32.5가 나왔다면? N은 33이 되어야합니다

즉 좌항을 올림하면 N을 구할 수 있습니다.

올림은 math의 ceil 함수를 사용합니다.

import math
def snail(day, night, height):
    # height에 도달할 때는 day가 night보다 하나 더 많은 상태
    # height <= n*day - (n+1)*night = n(day - night) + night
    # (height - night) / (day - night) = n
    cnt = (height - night) / (day - night)
    return math.ceil(cnt)
lst = list(map(int,input().split()))

print(snail(lst[0],lst[1],lst[2]))