[브론즈1]백준 2869번(달팽이는 올라가고 싶다) - 코테공부 37일차(2025.02.27)

문제유형

수학

풀이 방법 도출 과정

1. 땅 위의 달팽이가 V미터인 나무 막대를 올라간다. 달팽이는 낮에 A미터 올라가는데 밤에는 B미터 떨어진다. 달팽이가 나무 막대를 모두 올라가려면, 몇일 걸리는지 구하는 문제

2. 입력: A, B, V

 

3. 예제 분석

1일차: (A - B)

2일차: (A - B) + (A - B)

3일차: (A - B) + (A - B) + (A - B)

일반화 하면 (A - B) x (n - 1) + A

 

4. 이식을 변형하면  (A - B) x (n - 1) + A >= V

이것을 n에 관하여 정리하면 다음과 같아진다. n >= V-A/A-B + 1 그런데 이가 마지막 날에는 미끌어지지 않기 때문에 +1를 삭제한다.

시간 복잡도

시간 복잡도는  O(1)이다. 

코드 및 간단설명

수학을 사용하였다.

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

n = math.ceil((V - B) / (A - B))
print(n)

다른 풀이

1)  다른 구현 방법

달팽이는 마지막 날 낮에 정상에 도달하므로, 마지막 날에 올라갈 a를 미리 빼서 그 전까지 올라가야 하는 거리를 v에 저장하는 방법을 사용해서 시간복잡도를 더욱 줄이는 방법도 있다. 

a, b, v = map(int, input().split())
v -= a
print((v-1) // (a-b) + 2)