[Coding Test][Python] 백준 2869번: 달팽이는 올라가고 싶다.

문제

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

 

코드

import sys
a, b, v = map(int, sys.stdin.readline().split())

d = (v-b-1)//(a-b) + 1
print(d)

가장 직관적인 방법은 while 반복문을 돌며 하루하루 올라가고 미끄러지는 과정을 반복하는 것이다. 

하지만 문제의 제한 시간이 0.25초 이내라는 점에서, 시간 초과를 고려한 풀이법이 필요했다.

 

첫 시도

반복문을 없애기 위해 달팽이의 움직임을 수학 수식으로 모델링해 보았다.

달팽이가 정상에 도달하는 데 걸리는 일수를 x라고 하자.

달팽이는 낮에 올라가고 밤에 미끄러지지만, 마지막 날에는 정상에 도달한 후 미끄러지지 않는다.

즉 x일 동안 A미터씩 올라가는 것은 x번, B미터씩 미끄러지는 것은 (x-1)번 일어난다.

이를 방정식으로 세우면 다음과 같다.

Ax - B(x-1) = V
Ax - Bx + B = V
x(A - B) = V - B
x = (V-B)/(A-B)

 

이 공식을 코드로 옮기면 다음과 같이 한 번의 나눗셈으로 며칠이 걸리는지 바로 알 수 있다.

import sys, math
a, b, v = map(int, sys.stdin.readline().split())

x = (v-b)/(a-b)
print(math.ceil(x)) # 소수점이 나오면 하루가 더 필요한 것이므로 올림 처리

 

개선

파이썬에서 / 연산자는 결과를 실수형으로 반환한다. 파이썬은 내부적으로 정밀도가 높지만 컴퓨터가 실수를 표현할 때는 근사치를 사용하기 때문에 미세한 오차가 발생할 수 있다. (실무에서 double이나 float를 무심코 사용한다면 1원이 비거나 더해지는 치명적인 정산 오차가 발생할 수 있다)

 

따라서 이런 오차 가능성을 원천 차단하려면 math.ceil과 실수 나눗셈( / )을 버리고 오직 정수형(integer) 연산만으로 올림을 구현해야 한다.

수학적으로 X를 Y로 나눈 올림값은 순수 정수 나눗셈만 사용하여 다음과 같이 구할 수 있다. (단, X,Y > 0)

올림 몫 = (X-1 / Y) + 1 

이 공식을 대입해 작성한 최종 식 코드는 다음과 같다.

days = (v - b - 1) // (a - b) + 1