[2869] 백준 문제풀이 - 달팽이는 올라가고 싶다

https://www.acmicpc.net/problem/2869

문제

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

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

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

입력

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

출력

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

풀이

1. 오답(타임 아웃) ```py A, B, V = map(int, input().split(“ “))

total = 0 day = 0 while total < V: if total + A >= V: total = total + A else: total = total + A - B day += 1

print(day)

위와 같은 코드는 쉽게 짤 수 있다. V(높이)에 도달하기전까지 ``total``에 ``total = total + A -B``를 해주고 V에 도달하면 반복문을 벗어나고 ``day``를 출력한다. 하지만 이건 문제의 범위의 끝 $V <= 1,000,000,000$ 을 대입해보면 타임 아웃이 일어나서 오답처리된다.

2. 정답
```py
A, B, V = map(int, input().split(" "))
print(((V - A) - 1) // (A - B) + 2)

일반적으로 타임 아웃을 일으키지않게하려면 반복문을 사용하지 않아야한다. 즉 답을 식을 세워 찾아주어야 한다. 이 때 쉽게 생각할 수 있는 것은 $(V-A)//(A-B)$ 다. 정상에 올랐을 때의 날의 미터를 뺀 $V-A$에서 하루에 오르는 미터$(A-B)$를 나눴을 때의 몫을 구해준다. 이렇게 하고 정상에 오르는 날 하루$+1$을 해주면 쉽게 풀어질 것 같지만 $(V-A)\%(A-B)$ 즉, 저 식의 나머지가 있을 경우 하루를 더 해주어야하는 오류가 발생하게된다. 그렇다고 이 오류를 잡기위해 +1을 더해주면, 나머지가 생기지 않을 경우의 답이 나오지 않는다. 그래서 $(V-A)$에 $-1$을 더 해줌으로 나머지를 일부러 발생시킨 후, 2일을 더해주면 문제가 쉽게 해결된다.