달팽이는 올라가고 싶다

Reference

• 백준 2869번

문제 풀이

이 문제를 푸는데 있어 중요한 키워드는 다음과 같다.

• 매일
• 올라가고 (+)
• 미끄러지고 (-)
• 목표 높이까지 (조건문 and 반복문)

이 점에 착안하여 현재 위치를 저장할 변수와 날짜를 카운트할 변수를 선언, 초기화해주고 최종적으로 카운트를 출력해주면 해결할 수 있다.

A, B, V = map(int, input().split(" "))

position = 0
dayCount = 0

while position < V:
    dayCount += 1
    position += A
    if position >= V:
        break
    position -= B

print(dayCount)

 

하지만 이런 단순한 풀이로는 시간복잡도를 통과할 수 없다. 언제나 그렇듯...

예제 입력 100 99 1000000000(...) 이 입력되게되면 시간복잡도 = O(n)

 

따라서 우리는 좀 더 스마트하게 해결해야하고 내가 생각한 해결과정은 다음과 같다.

• V - A 는 마지막날 전까지 이동한 총거리이다.
• A - B 는 하루동안 이동할 수 있는 거리이다. (낮 이동 거리 - 밤 미끄러지는 거리)
• 따라서 (V - A)/(A - B) 를 하게 되면 마지막날 낮동안 이동할 수 있는 거리를 제외하고 현재까지 이동한 총 날짜가 나올 것이다.

코드로 작성해보자.

import math

A, B, V = map(int, input().split(" "))

X = V - A
Y = A - B

dayCount = math.ceil(X / Y + 1)

print(dayCount)

 

X, Y는 inline으로 처리해도 되지만, 이렇게 작성하는 것이 보기 좋은 것 같아서 따로 빼두었다.

 

알아두면 도움되는 것들

• math
• ceil (올림), floor (내림)