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

문제#

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

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

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

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

입력#

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

출력#

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

풀이#

이 문제에서 가장 중요한 점은 정상에 도달한 날에는 밤에 미끄러지지 않는다는 것입니다.

처음에는 하루에 올라가는 양이 A - B 이므로 단순히 V / (A - B) 처럼 계산하고 싶어집니다.
하지만 마지막 날은 조금 다르게 생각해야 합니다.

달팽이는 마지막 날 낮에 A미터를 올라가서 정상에 도달하면 끝납니다.
즉, 마지막 날 이전까지는 전체 높이 V가 아니라 V - A까지만 도달해 있으면 충분합니다.

하루가 완전히 지나면 실제로 늘어나는 높이는 다음과 같습니다.

따라서 마지막 날 전까지 필요한 일수는 다음과 같습니다.

여기에 마지막 날 하루를 더하면 전체 날짜는

이 됩니다.

정수 연산에서는 올림을 직접 사용할 수 없으므로, 다음 공식을 이용합니다.

이를 그대로 대입하면

이므로 최종 식은 다음과 같습니다.

예를 들어 A = 2, B = 1, V = 5 라고 해보겠습니다.

• 마지막 날 전까지 필요한 높이: V - A = 3
• 하루 순증가량: A - B = 1

따라서 마지막 날 전까지 3일이 필요하고, 마지막 날 1일을 더해 총 4일이 됩니다.

실제로 진행해보면

• 1일차 낮: 2, 밤: 1
• 2일차 낮: 3, 밤: 2
• 3일차 낮: 4, 밤: 3
• 4일차 낮: 5 도달

로 확인할 수 있습니다.

이 문제는 반복문으로도 구현할 수 있지만, V의 범위가 매우 크기 때문에 단순 시뮬레이션은 비효율적입니다.
따라서 수식을 이용해 한 번에 계산하는 방식이 적절합니다.

코드#

1
#include <stdio.h>
2

3
int main() {
4
    int a, b, v;
5

6
    scanf("%d %d %d", &a, &b, &v);
7

8
    int days = (v - a + (a - b) - 1) / (a - b) + 1;
9

10
    printf("%d\n", days);
11
    return 0;
12
}