백준(BAEKJOON): 달팽이는 올라가고 싶다(2869번)

Source

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 1 5

예제 출력 1

4

해설

처음에는 매우 간단한 문제라고 생각했다. 왜 이런 문제가 <수학1>로 분류되었을까란 의구심이 살짝 고개를 들었지만....

첫 번째 코드이다.

#include <stdio.h>
int main(int argc, char *argv[])
{
    int move_day, move_night, height, days = 1;
    int move_sum = 0;

    scanf("%d %d %d", &move_day, &move_night, &height);

    while (1) {
        move_sum += move_day;
        if (move_sum < height) {
            move_sum -= move_night;
        } else {
            break;
        }
        days++;
    }

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

코딩을 하면서도 루프로 돌릴 게 아니라 간단한 수식을 찾아야 하는 거 아니야 하는 생각이 들었지만 이번에도 무시했다. 이 간단한 연산과 루프에 얼마나 시간이 걸리겠어? 루프로 돌리면서 정상에 오른 날에는 미끄러지지 않는다는 점을 if문으로 처리했다. 출력이 정확하니 이제 채점을 받아볼까? 결과는 시간 초과였다. 문제를 다시 살펴보니 시간 체한이 0.15 초 (추가 시간 없음)였다. 결국 루프를 돌리지 말라는 이야기다.
하루 이동 거리는 간단한데 정상에 올랐을 때는 미끄러지지 않는다는 점을 수식에 어떻게 반영할 수 있을까? 하루 이동 거리는 올라간 거리(move_day)에서 미끄러진 거리(move_night)를 빼면 된다. 그런데 정상에 오른 날 미끄러지지 않는다는 건? 우리가 알고 앂은 건 달팽이의 매일 이동 거리의 누계라고 할 때 마지막날에는 이 누계에서 미끄러진 거리가 제외된다는 의미이므로 전체 거리 height에서 미끄러진 거리(move_night)를 빼면 우리가 원하는 이동 거리 누계가 된다. 따라서 전체 이동할 거리(height - move_night)를 매일 이동 거리(move_day - move_night)로 나누면 달팽이가 며칠 만에 정상에 오르는지 알 수 있다.

    days = (height - move_night) / (move_day - move_night);

이때 유의해야 하는 것은 나눗셈이 정수로 떨어지지 않은 경우는 하루가 더 추가된다는 점이다. 이 부분을 아래와 같이 따로 처리해 주어야 한다.

if((height - move_night) % (move_day - move_night) != 0) {
        days++;
    }

다시 완성한 코드는 아래와 같다. 이번 코드는 당연히 시간 제한에 걸리지 않았다.

소스코드

#include <stdio.h>
int main(int argc, char *argv[])
{
    int move_day, move_night, height, days;

    scanf("%d %d %d", &move_day, &move_night, &height);

    days = (height - move_night) / (move_day - move_night);

    if((height - move_night) % (move_day - move_night) != 0) {
        days++;
    }

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