[알고리즘][파이썬] 백준_2869번_달팽이는 올라가고 싶다

달팽이가 있다.

변수 A는 낮에 기어 올라가는 거리,

변수 B는 밤에 잘때 미끄러지는 거리,

변수 V는 정상이며, 정상에 도달할 경우 밤에 미끄러지지 않는다.

이때 정상에 몇일만에 도착할 수 있는지 출력해야 한다.

---

1차 시도

# 1차시도(결과: 시간 초과)
A, B, V = map(int, input().split())

per = 0 # 달팽이의 performance 변수
days = 1 # 구하고자 하는 정상 도달일 변수(기본값을 1일로 주었다)

while 1:
    per += A
    if per >= V:
        break
    per -= B
    days += 1

print(days)

 

예제의 값을 입력하여 출력하니 결과값은 동일하게 출력되었다.

하지만 예제 입력 3번(100 99 1000000000)의 경우 매우 오랜 시간이 걸렸다.

그럼에도 불구하고 제출하였으나 결과는 "시간 초과".

---

2차 시도

# 반복문 대신 수식을 이용하였다.
A, B, V = map(int, input().split())

days = (V - B) // (A - B)
if (V - B) % (A - B) > 0: # if문을 이용하여 나머지의 올림을 구현하였다.
    days += 1
    
print(days)

 

성공!

---

해결한 방법

반복문은 시간복잡도가 높아 문제를 해결할 수 없었다.

그래서 수식을 이용하였다.

달팽이가 밤에 미끄러지지 않는다면 매우 간단한 수식이다.

예) 달팽이가 밤에 미끄러지지 않을 경우, 하루 이동 거리 2미터, 정상 6미터 라면,
6 / 2 = 3
따라서 3일 걸린다.

 

하지만 이 문제에서 달팽이는 밤에 미끄러진다.

그래서 수식이 다소 복잡해 진다.

예) 달팽이가 밤에 미끄러지는 경우, 낮에 이동 거리 2미터, 밤에 미끄러 지는 거리 1미터, 정상 6미터 라면,
6 - 1 / 2 - 1 = 5
따라서 5일 걸린다.

 

위 수식을 코드에 적용하면,

days = (V - B) // (A - B) # 몫은 정상에 도달한 일수
if (V - B) % (A - B) > 0: # 나머지가 존재한다면 1일을 추가
    days += 1

 

if문 대신에 파이썬의 math.ceil을 이용해 나머지를 올림 처리, 제출해 보았다.

제출 결과 처리 시간은 거의 비슷했으나, 메모리는 if문 적용시 더 적게 사용했다.

# if문 대신 math.ceil을 이용해 나머지 올림 처리
import math

A, B, V = map(int, input().split())
days = math.ceil((V - B) / (A - B))
    
print(days)