[알고리즘 문제 풀이][수학] 백준 2869번 - 달팽이는 올라가고 싶다

초코쨔응 2021. 9. 23. 01:43

백준 2869번 달팽이는 올라가고 싶다 문제입니다.

(기초 수학 문제)

- 문제 설명: https://www.acmicpc.net/problem/2869

- 문제 풀이:

달팽이는 낮에는 막대를 오르지만, 밤에는 잠을 자는 동안 아래로 미끄러집니다. 그래서 총 거리를 오르기 위해서 총 며칠이 소요되는지를 구하는 문제입니다. 입력은 오르는 높이 (A), 미끄러지는 높이 (B), 총 거리 (V) 가 주어집니다. 문제의 조건은 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 이기 때문에 미끄러지는 높이가 오르는 높이보다 더 길다거나, 총 거리보다 더 많이 오를 수 있지는 않습니다.

다만, 문제 풀이에 주의해야할 점은 마지막 날의 낮에 정상에 오르게 되면 이미 도착했기 때문에 미끄러지지 않는다는 것입니다.

입력

2 1 5

출력

전체 거리가 5인 경우, 첫날 2만큼 오른 후 밤에 1 미끄러져서 총 1 높이에 있게 됩니다.

다음날 2 만큼 오른 후 밤에 1 미끄러져서 총 2 높이에 있게 됩니다.

그 다음날도 2 만큼 오른 후 밤에 1 미끄러져서 총 3 높이에 있게 됩니다.

마지막 날에 2만큼 오르면 정상에 도달 (5) 하기 때문에 이 날까지 총 4일이 걸리게 됩니다.

- 코드:

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

step = A - B
dist = V - A
ans = 1 + (dist // step) + int(not(not(dist % step)))

print(ans)

마지막 날에는 미끄러지지 않기 때문에 올라간 것만 고려해서 V - A 로 거리를 수정하고 그 날 올라간 것을 고려하여 1을 미리 더해주었습니다.

그리고 마지막 날 전에는 하루에 (A - B) 만큼 올라갈 수 있으므로 1 + (V - A) / (A - B) 가 됩니다.

그런데, (V - A) 가 (A - B) 로 딱 나누어 떨어지지 않을 수 있기 때문에 나머지가 있는 경우 +1 일이 더해질 수 있도록 % 가 있는 경우 뒷 부분에 따로 처리를 해주었습니다. (dist % step 부분)

※ (V - B - 1) / (A - B) + 1 설명: https://www.acmicpc.net/board/view/22313
마지막 날에는 미끄러지지 않기 때문에 V - A 대신 V - B 접근법도 가능하다고 합니다.

※ 나누어 떨어지는 부분을 제 코드처럼 따로 고려하지 않고 바로 위와 같이 간단한 식으로 한 번에 처리 가능한 이유: https://www.acmicpc.net/board/view/53443 혹은 https://www.acmicpc.net/board/view/44742

※ 현재 시간 제한으로 이분 탐색 코드도 가능한지는 확인이 필요합니다.