[백준] #2869 달팽이는 올라가고 싶다 (Python3)

 

시간 제한	메모리 제한
0.15 초 (추가 시간 없음)	128 MB

문제

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

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

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

입력

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

출력

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

 

예제 입력 1	예제 출력 1
2 1 5	4

 

풀이

1. 식 세우기 

Ax -B(x-1) >= V 일 때, x의 값

B에 x-1을 하는 이유는 한 번 정상에 올라가면 내려오지 않는다.

 

▼ 시간초과 코드 - 반복문으로 설계한 코드

 반복문 day값을 1씩 올리면서 찾으면, 2 1 1000000 값을 입력했을 때, 시간초과된다.
시간 제한은 0.15초 이다.

import sys
A,B,V = map(int,sys.stdin.readline().rstrip().split())

day = 1
while True:
    if (A-B)*day + B >= V: print(day); break
    day += 1

 

2. x를 좌항에 남기고 x에 대한 부등식으로 수정

x >= (V-B)/(A-B)  을 만족하는 x의 값

파이썬의 math.ceil 함수를 이용해서 나눈 결과를 올림하여 x값을 정한다.

import sys,math
A,B,V = map(int,sys.stdin.readline().rstrip().split())

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