파이썬 달팽이는 올라가고 싶다(백준 BOJ 2869)

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 1 5

예제 출력 1

4

예제 입력 2

5 1 6

예제 출력 2

2

예제 입력 3

100 99 1000000000

예제 출력 3

999999901

📝 풀어보기

문제를 처음 봤을 땐 굉장히 쉬워보였다.

# A : 올라가는 거리 B : 미끄러지는 거리 V : 정상 위치
A, B, V = map(int, input().split())
cnt = 0 # 올라가기까지 걸린 일수
height = 0 # 올라가는 거리를 누적하기 위한 변수

while True:
    cnt += 1 # 일수 증가
    height += A # 높이 누적
    if height == V: # 높이가 정상 위치가 같을때 
        print(cnt) # 누적일수를 출력
        break
    height -= B # 밤에 B만큼 미끄러짐

하지만 문제는 시간 제한이었다. 이러한 경우는 짧은 범위의 계산은 빠르게 이뤄지지만 예제 입력 3같은 경우에는 시간이 너무 오래걸려 시간 초과가 발생한다.

✏️ 수정하기

📌 시간을 줄이기 위해 부등호로 비교를 하고 출력하는 방식은 사용하면 안된다. 먼저, sys 와 math 를 import한다.

import sys # readline()으로 입력받기위해
import math # 소수점 올림을 하기위해

📌 A : 올라가는 값, B : 미끄러지는 값, V : 정상 값 변수를 지정하고 sys.stdin.readline() 로 입력받는다. sys.stdin.readline()은 input()에 비해 반복적으로 여러개를 입력 받을때 더 빠르게 처리한다.

📌 c 에 (V-B) [정상값-미끄러지는값]/(A-B) [오르는값-미끄러지는값] 을 계산한다. V /(A-B)를 할 경우에는 정상 도착시 미끄러지는 값이 반영되지 않는다.

📌 print(math.ceil(c)) 로 올림된 값을 출력한다. (V-B)/(A-B)를 그대로 출력할 경우에 분수의 계산이기때문에 소수점이 나오는데, 일자에는 소수점이 없기때문이다.

A, B, V = map(int, sys.stdin.readline().split())
# A미터를 올라가고 B미터를 미끄러진다. 정상의 높이는 V미터
c = (V-B)/(A-B) # 정상-미끄러지는값 / 오르는값-미끄러지는값
                # (5-1) = 4 / ( 2-1 )= 1 = 4)
print(math.ceil(c))

전체 코드

import sys
import math

A, B, V = map(int, sys.stdin.readline().split())
# A미터를 올라가고 B미터를 미끄러진다. 정상의 높이는 V미터
c = (V-B)/(A-B) # 정상-미끄러지는값 / 오르는값-미끄러지는값
                # (5-1) = 4 / ( 2-1 )= 1 = 4)
print(math.ceil(c))