백준 2869번 파이썬 문제풀이(기본수학 - 달팽이는 올라가고 싶다) -상세풀이

-> 이 문제의 키포인트는 무엇일까? 입력받는 수의 범위가 10억까지인데 시간제한은 0.15초이다. 즉, 반복문으로 풀라는 소리가 아니다. 그러면 수학적 식을 찾아야하는데 식을 어떻게 찾을 수 있을까?

 

a(낮에올라가는높이) , b(밤에 미끄러지는 높이) , v(올라가야되는 높이),count(마지막날을 제외한 올라간 횟수) 를 놓고 식을 짜보겠다. 

v <= (a-b * count) + a 이다. 즉 무엇이냐면 v(올라가야되는 높이) 보다 ((a-b):하루에 올라갈 수 있는 높이) * (마지막날을 제외한 횟수)에 마지막날 a만큼 오르는 것을 더해준 값이 더 커야 한다는 거다. 

 

이를 식을 이항 정리를 하면 (v-a)/(a-b) <= count 가 나온다. 즉, (마지막날을 제외한 횟수는) (v-a)/(a-b) 보다 같거나 커야한다는 말이다.

 

그럼 여기서 마지막날까지 횟수를 포함시키기 위해선 (v-a)/(a-b) + 1 만 해주면 된다.

정리하면 (v-a)/(a-b) +1<= count +1 (count+1은 마지막날까지 포함한횟수) 이다.

 

이를 다시 result(==count+1)로 정리해보면 (v-a)/(a-b) +1<= result  로 정리할 수 있다. 결국 이 result 값(출력할 총 횟수)이 (v-a)/(a-b) +1 보다 크면 된다는 것이다.

 

하지만 여기서 한가지 더 생각해야 할 점이 있다. 만약에 (v-a)/(a-b) + 1 이 1.25 , 2.5 와 같이 소수점으로 나오면 어떻게 해야하는가? 그러면 정답이 result값(총 횟수)은 2번하고 0.5번만 수행하면 되는건가? 이것은 아니다. 횟수라는 건 자연수 이기 때문에 즉 1.25는 2번, 2.5는 3번 이기때문에 result값을 구하기 위해서는 (v-a)/(a-b) + 1 값에 올림함수를 써줘야한다.

따라서 답은 다음과 같다.

 

import math

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

print(math.ceil((v-a)/(a-b)+1)) #올림함수 사용