[Python 3] BOJ - 2869 "달팽이는 올라가고 싶다"
# 문제 링크 : https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽
www.acmicpc.net
# 풀이 :
이 문제는 이분탐색으로도 풀 수 있지만 본 포스팅에서는 수학적 접근법으로 풀이하겠다. 가장 중요한 조건은 정상에 오른 순간(혹은 초과한 순간) 더이상 떨어지지 않는다는 점이다.
만일 7칸 올라가야 하는데 낮에는 3칸 올라가고 밤에 1칸 떨어진다면, 하루를 낮부터 시작하여 밤까지로 생각할 때, 하루에 갈 수 있는 칸 수는 2칸이다. 따라서 첫째 날은 2번째 칸까지 이동하고 둘째 날은 4번째 칸까지 이동한다. 그런데, 세번째 날 낮이 되는 순간 7번째 칸에 도착하므로 더이상 떨어지지 않으므로 3일만에 도달할 수 있다. 따라서, (N - A), 즉 낮만에 정상에 도달 할 수 있는 칸을 (A - B), 하루만에 갈 수 있는 거리로 나누었을 때, 나머지가 0이라면 정확히 (N - A)번째 칸에 갈 수 있다는 것이고, 그렇지 않다면 (N - A)에 갈 수 없다. 따라서 나머지가 0이라면 마지막에 낮만큼만 가면 되기 때문에 정답이 (N - A) // (A - B) + 1이 되고, 나머지가 0이 아니라면 (N - A) // (A + B) + 2를 해주면 된다.
위 그림에서 3번째 칸에 도달해야 그다음날 낮에 정상에 도달할 수 있다. 그러나, 우리는 하루를 '낮부터 밤까지'로 정의했으므로 3번째 칸에 도달하려면 1.5일이 소요된다. 그러나, 이는 우리가 정의한 하루를 위반하게 되므로 어쩔 수 없이 하루를 더 기다려야 한다. 그래서 1을 더해주게 되는것이다. 그런데, 4번째 칸에 도달해도 그다음날 낮에 정상에 도달할 수 있으므로 또 1을 더해주면 된다. 따라서 1을 두번 더하니 총 2를 더해주면 나머지가 0이 아닌 경우에도 정답을 구할 수 있다.
# 코드
import sys
# 입력부
a,b,v = map(int, sys.stdin.readline().split())
# res = V - A칸 만큼 갈 수 있는 일수
res = (v - a) // (a - b)
if (v - a) % (a - b) == 0:
print(res + 1)
else:
print(res + 2)