[구현/수학] 백준 2869 달팽이는 올라가고 싶다 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 아침에 A만큼 올라가고, 밤에 B만큼 내려가는 달팽이가 있습니다. 높이 V미터까지 올라가는 데 며칠이 걸리는지 구하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 

 

 

3. 코드

A, B, V = map(int, input().split())
day = 0
h = 0 #높이
while True:
    day += 1
    h += A #낮에 A만큼 올라감
    if h >= V: # 다 올라가면 종료
        break
    h -= B #밤에 B만큼 내려감
print(day)

 단순히 문제대로 구현하면 시간 초과가 납니다.. 시간 제한이 0.15초로 살벌하죠..

 

 

A, B, V = map(int, input().split())
#하루만에 다 올라감
if V < A:
    print(1)
else:
    day = (V-B) // (A-B) # V를 올라가는 데 걸리는 날짜 (정상에 도달하면 밤에 내려오는 B는 뺌)
    if (V-B) % (A-B) == 0:
        print(day)
    else: #나머지가 있으면 다음날에 완주
        print(day+1) 

 하루하루 덧셈하면 O(n)이지만 한 번에 나누면 O(1)입니다. 하룻동안 올라가는 만큼으로 V를 나누어서 걸리는 일 수를 구해줍니다. 이 때, V-B를 해줘서 정상에 올라갔을 때 밤에 내려오는 높이를 빼줍니다.