2869 달팽이는 올라가고 싶다
TLDR#
f: (a-b)x >= (v-a)를 만족하는 최소 x를 구하는 문제
Snippet#
"""
boj.kr/2869
f: (a-b)x >= (v-a)를 만족하는 최소 x를 구하는 문제
"""
from math import ceil
def main(a, b, v):
x = ceil((v-a) / (a-b))
return x + 1
if __name__ == "__main__":
a, b, v = map(int, input().split())
print(main(a, b, v))
Sample Input & Expected Output#
Input#
2 1 5
5 1 6
100 99 1000000000
Expected Output#
4
2
999999901
Notes#
- 처음에는
f: (a-b)x < (v-a)
또는f: (a-b)x < (v-b)
로 최대 x를 찾는 문제인 줄 알아서 계속 삽질을 했다. - 달팽이의 위치가 v-a 보다 커질때까지 도달하는데 걸리는 시간만 계산하면 그 시간에 1을 더하는 문제였다는 것을 알아냈다.
- 그러니까 x는 달팽이의 위치가 v-a 보다 커지는 첫번째 순간을 포착해야 하고, 정확하게 나누어 떨어지지 않는 경우, 올림을 수행해야 v를 넘어서 올라가는 날이 없게된다.