[파이썬/Python] 백준 2869번 달팽이는 올라가고 싶다

[파이썬/Python] 백준 2869번 달팽이는 올라가고 싶다

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

---

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

예제 입력 1

2 1 5

예제 출력 1

4

예제 입력 2

5 1 6

예제 출력 2

2

예제 입력 3

100 99 1000000000

예제 출력 3

999999901

풀이 1

math.ceil

import sys
import math
input = sys.stdin.readline

# 입력
a, b, v = map(int, input().split())

# 달팽이가 첫 날에 바로 정상에 도착한다면 1을 출력
# a - b : 달팽이가 하루에 오를 수 있는 길이
# v - a : 마지막 날을 제외
# 소수일 경우 하루로 취급, 마지막날을 다시 더해줌
print(1) if v == a else print(math.ceil((v-a) / (a-b))+1)

이 코드는 입력을 받은 후 간단한 수식을 이용하여 답을 구하므로, O(1)의 시간 복잡도를 가진다. 입력 크기에 관계없이 일정한 시간이 소요된다.

풀이 2

집합을 이용한 탐색

# 입력
a, b, h = map(int, input().split())

# h - b - 1 :
# 첫번째 낮을 시작하기 전에는 아직 달팽이가 미끄러지지 않기 때문에, b를 빼줌.
# 1을 빼는 이유는 달팽이가 정상에 도착하기 전 마지막 날 계산
# a - b : 달팽이가 하루에 올라갈 수 있는 높이
# 마지막에 마지막 날을 더해줌
print((h - b - 1) // (a - b) + 1)

이 코드는 입력을 받은 후 간단한 수식을 이용하여 답을 구하므로, O(1)의 시간 복잡도를 가진다. 입력 크기에 관계없이 일정한 시간이 소요된다.

 

최대한 라이브러리를 사용하지 않고 풀도록 노력해야 될 것 같다. 라이브러리를 사용하지 않아도 풀 수 있는 방법이 있다면, 그게 코테를 준비하는 데에는 훨씬 유리할 것이다.

 

참고자료

로그인

12_반올림, 내림, 올림