[python] 2869. 달팽이는 올라가고 싶다

• 문제

---

---

 

• 잘못된 풀이

# 시간 초과 코드
total = 0 # 달팽이가 올라간 높이 (height)
cnt = 0 # 정상까지 걸린 기간 (day)
while True:
    cnt += 1
    total += A
    if V <= total:
        break

    total -= B
    if V <= total:
        break
print(cnt)

 

문제가 단순하다고 생각할 수 있지만

• "정상에 올라간 후에는 미끄러지지 않는다"
• 시간 제한: 0.15초

라는 점에서 생각보다 문제가 까다롭다고 느꼈다.

이 때문인지 낮은 난이도에 비해 정답 비율도 29.5333% 밖에 되지 않는다.

 

나는 처음 문제 풀이를 할 때 올라간 경우에 한번, 미끄러질 때에 한 번  달팽이가 정상에 도착했는지 체크해주면 된다고 생각했다.

때문에 다음과 같이 while문 안에 if문을 두 개나 작성했고, 시간초과로 문제를 맞추지 못했다.

 

• 올바른 풀이

# 정답 코드
import math
A, B, V = map(int, input().split())
cnt = (V-B) / (A-B) # Ax-B(x-1) >= V 
print(math.ceil(cnt)) # 정상까지 걸린 기간 day

 

따라서 알고리즘 시간을 줄이기 위해,  while문을 없애야 한다고 생각했다.

그리고 앞선 코드와 다른 새로운 풀이 방법을 모색했다.

 

앞선 방법은 2개의 if문으로 올라갈 때 한번, 미끄러질 때 한번 

달팽이가 정상에 도달했는지 체크했다면 새로운 풀이 방법은 다음과 같다.

while True:
    cnt += 1  # 정상까지 걸린 기간 (day)
    total += A  # 달팽이가 올라간 높이 (height)
    
    if V <= total:
        break
    
    total -= B

print(cnt)

 

즉, 달팽이가 올라가고 난 후에 if문으로 정상에 도착했는지 확인해주는 것이다.

이를 한 줄로 작성하면 다음과 같다.

A*cnt - B*(cnt-1) >= V # cnt: 달팽이가 정상까지 걸린 기간 (day)

 

이를 cnt에 대한 식으로 수정하면 다음과 같다. 

cnt = (V-B) / (A-B) # A*cnt - B(cnt-1) >= V

 

cnt가 4.2일 처럼 소숫점이 나올 수 있기 때문에  math.ceil()을 통해 올림을 해주었다.