[Python][백준 BOJ Bronze I] 2869. 달팽이는 올라가고 싶다 : 반복문으로 인한 시간 초과 해결

❌ 접근 방식 1

낮과 밤에 각각 +2, -1만큼의 높이를 올라간다.
따라서 날짜를 처음에 카운트 하고 낮과 밤에 움직일 수 있는 높이를 각각 계산한 후,
높이가 V 이상이 되는 즉시 while문을 종료한 후 날짜를 출력한다.

import sys
a, b, v = map(int, sys.stdin.readline().split())
days = 0
h = 0

while True:	# h == v 일 때까지 무한루프
    days += 1

    h += a	# 낮
    if (h >= v):
        break

    h -= b	# 밤
    if (h == v):
        break
print(days)

결과는 시간초과.
이 문제의 시간 제한은 0.25초이기 때문에 반복문을 사용하지 않고 구현해야 한다.

✅ 접근 방식 2

반복문을 사용하지 않고 이 문제를 풀려면 어떻게 해야할까? .......
 
반복문을 사용했던 이유는 아래와 같다.
 

1. 하루에 오르내리는 높이와 days를 카운팅하면서 오르내리는 높이와 나무 높이 V를 비교하기 위함.
2. 비교해서 달팽이가 올라간 높이 h가 나무 높이 V 이상이 되는 즉시 break를 해 최소 days를 구하기 위함.

그렇다면 days를 증가시키며 찾지 말고, 아예 변수화 해버린 뒤에 찾아 보자.

 

부등식 도출 과정

낮에 정상에 올라갔다면 미끄러지지 않으므로 (-b 수행 X) 위와 같이 부등식을 도출했다.

 

반복문 없이 v <= (a - b) * days + b를 만족하는 days의 최소값을 구하려면?

일단 v == (a - b) * days + b를 만족하는 days의 값을 구해보자. (days = (v - b) / (a - b) 이용)

→ tc1) days == 5, tc2) days == 1.25

 

"몇 일" 걸리는지 출력해야 하므로 days가 정수일 경우 그대로 출력하고 소수일 경우 올림하여 정수형으로 출력하면 된다.

→ tc1) days == 5, tc2) days == 2

Solution 1. math.ceil() 이용

import sys
import math
a, b, v = map(int, sys.stdin.readline().split())

# v <= (a - b) * days + b 를 만족하는 days의 최솟값 출력
days = (v - b) / (a - b)
print(math.ceil(days))

Solution 2. int() 이용

import sys
a, b, v = map(int, sys.stdin.readline().split())

# v <= (a - b) * days + b 를 만족하는 days의 최솟값 출력
days = (v - b) / (a - b)
print(int(days) if days == int(days) else int(days) + 1)    # days가 정수가 아니라면 +1

---

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다