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

문제

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

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

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

입력

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

출력

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

 

 

 

---

처음에는 문제를 보자마자 스택으로 풀면되나? 스택이니 재귀를 사용해야겠지?

라고 생각했으나 문제의 조건에

 

길이가 최대 1,000,000,000 까지인걸 본 순간 재귀나 기타 반복문은 버리고 수학적으로 풀어야겠다 생각했다.

 

import sys
a, b, v = map(int, sys.stdin.readline().split())
cnt = 0
now = 0
if a == v:
    print("1")
else:
    now = v/(a-b)-a
    cnt = now/(a-b)
    while True:
        cnt += 1
        now += a
        if now >= v:
            print(int(cnt))
            break
        now -= b

처음에 푼 방식은

 

길이 / (올라가는 길이 - 내려가는 길이) - 올라가는 길이

 

위의 방법으로 정상에 도착하기 전날까지의 날짜를 구하는 방식으로 했다.

 

결과는 당연히

 

---

이후 계산식을 다시 써보았다.

 

(길이 - 내려가는 길이) / (올라가는길이 - 내려가는 길이)

위의 방법으로 계산하면 전날이 아닌

 

당일 낮에 올라간 길이까지 구할 수 있었다.

 

예제를 예시로 들면

 

2 1 5

(5 - 1) / (2 - 1) = 4 / 1 = 4

 

5 1 6

(6 - 1) / (5 - 1) = 5 / 4 = 1.2

 

두 결과값으로 보면

 

2 1 5 일때는 4일째 낮에 5만큼 올라갈 수 있다.

 

5 1 6 일때는 1일째 낮에는 4만큼 올라가고 다음날 낮에 올라가서 정상에 도착한다.

 

즉 정확히 나누어 떨어지면 해당 날이 정상에 오른날이며

소수점이 남는다면 그 다음날이 정상에 오른날 (소수점 올림)이 된다.

 

import sys
import math
a, b, v = map(int, sys.stdin.readline().split())
cnt = (v-b) / (a-b)
print(math.ceil(cnt))