[백준 알고리즘]2869번 "달팽이는 올라가고 싶다."

[백준 알고리즘]2869번 "달팽이는 올라가고 싶다."

문제

백준 2869번

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

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

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

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

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

예제 입력1
2 1 5

예제 출력1
4

예제 입력1
5 1 6

예제 출력1
2

예제 입력1
100 99 1000000000

예제 출력1
999999901

문제 풀이

이 문제는 처음 문제를 보았을 때 시간 제한을 고려하지 못하고 풀어버려서 실패를 많이 한 문제이다. 맨 처음 풀었던 코드는 다음과 같다.

a, b, v = map(int, input().split())
day = 0
days = 0
night = 0
while True:
    if day < v:
        day = night + a
        night = day - b
        days += 1
    else:
        break

print(days)

이 코드는 input data가 10억까지이고 예제 출력 3번을 보면 약10억 만큼 반복문이 돌기 때문에 당연히 시간 초과가 날 수 밖에 없다. 그래서 이 문제를 해결하기 위해서는 공식을 통해 문제를 해결해야 겠다고 생각했다.

달팽이가 n일 후에 도달한다고 하면, (a n) - (b (n - 1)) >= v 이 식이 성립해야 하며, a, b, v가 모두 상수이므로 n을 기준으로 정리하면 n >= (v - b) / (a - b) 이다.

만일 (v - b) / (a - b) 값이 정수이면 n의 최소값은 n = (v - b) / (a - b) 이고, (v - b) / (a - b) 값이 4.1 처럼 소수점이 발생하면 n 은 5가 되어버린다. 다시 말해, int((v - b) / (a - b)) + 1이 된다. 이를 염두해보고 문제를 풀어보면 다음과 같이 풀 수 있다.

a, b, v = map(int, input().split())
k = (v - b) / (a - b)
if k == int(k):
    print(int(k))
else:
    print(int(k) + 1)