[알고리즘] 백준 2869 - 달팽이는 올라가고 싶다 (파이썬)

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

2869번: 달팽이는 올라가고 싶다

 

 

문제

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

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

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

입력

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

출력

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

풀이

처음에 시간 제한을 확인하지 않고 풀었다가 시간 초과 나는 것을 확인하고, 특정한 계산법이 있을 것이라는 생각이 들었다. 오답이었던 코드는 아래와 같다.

 

A, B, V = map(int, s.readline().split())

현재높이 = 0
DAYS = 0

while 현재높이 < V:
    DAYS += 1
    현재높이 += A
    if 현재높이 >= V:
        break
    현재높이 -= B

print(DAYS)

 

달팽이는 낮에 A만큼 올라가고 밤에 B만큼 떨어진다. 라는 말로 보아 하루에 올라가는 높이는 A - B이다.

총 올라가야 할 높이는 V이므로 V / (A - B) 라고 생각했지만, 총 올라가야 할 높이엔 미끄러지는 높이도 포함되어 있으니 (V - B) / (A - B) 라는 것을 알 수 있었다. 즉, 미끄러지는 거리를 뺀 높이가 총 올라야할 높이인 것이다. 그리고 DAYS가 실수일 경우 math.ceil()을 사용해서 올림해준다. (예를 들어 4.3 일은 존재하지 않으므로 5일을 출력한다) 정답 코드는 아래와 같다.

 

A, B, V = map(int, s.readline().split())

DAYS = math.ceil((V - B) / (A - B))
print(DAYS)