[백준] 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에 도달하기위해서 며칠이 걸리는지... 처음에 그냥 의식이 시키는대로 코드를 구현해 보았다.

import sys

def calc(a,b,v):
    move = 0
    day = 0
    while True:
        move += a
        if move >= v:
            break
        move -= b
        day += 1
    return day


def main():
    a, b, v = sys.stdin.readline().split()
    a=int(a); b=int(b); v=int(v)
    print(calc(a,b,v))

if __name__ == "__main__":
    main()

당연히 마지막 테스트케이스에서 타임오버가 나타난다.

따라서 브루트 포스방법으로 푸는건 아닌데,,, 어떻게 해야하나 싶었다.

 

생각하기를,,,

달팽이가 하루에 a-b만큼 이동한다. 그리고 마지막에 도착했을경우에는 b만큼 후진 하지 않기때문에 v-b만큼의 값이 얻어진다. 따라서 v-b의 값을 a-b로 나눈값이 총 이동한 날이 될것이다. 그러나 (v-b) / (a-b)의 값이 딱 나눠떨어지지 않는 경우가 존재하기 때문에 나는 여기서 python의 math모듈에서 소수점을 올리는 ceil()함수를 통해 나눠떨어지지 않는 경우를 처리하였다.

---

코드

"""
백준 알고리즘 2869번: 달팽이는 올라가고 싶다.
https://www.acmicpc.net/problem/2869
"""
import sys, math

def calc(a,b,v):
    # a-b: 달팽이가 하루동안 이동한 길이
    # v-b: 도착한 날에 후진하는 b를 뺀 값
    day = (v-b) / (a-b)

    # 나눠떨어지지 않은 경우를 위한 소수점 올리 처리
    return math.ceil(day)


def main():
    a, b, v = sys.stdin.readline().split()
    a=int(a); b=int(b); v=int(v)
    print(calc(a,b,v))

if __name__ == "__main__":
    main()