[백준 / C++] 2869. 달팽이는 올라가고 싶다.

문제

풀이

첫 번째 시도

#include <iostream>

using namespace std;

int main() {
    // 하루(for 문 1 reps) 동안 V(목표량)을 향해
    // A만큼 오르고 (진행상황에 올림)
    // 정상인지 체크하고(진행상황 >= 목표량), 정상이면 멈춤
    // 정상 아니면 B만큼 깎고 (진행상황 깎음)
    // 반복

    int a, b, v,reps = 0;
    int current = 0;

    cin >> a >> b >> v;

    while (true) {
        reps++;
        current += a;
        if (current >= v) {
            cout << reps << endl;
            break;
        }
        current -= b;
    }

    return 0;
}

알고리즘 풀이에 익숙하지 않아, 시간제한이 타이트한 것을 보고도 일단 머릿속에 가장 먼저 떠오르는 방식으로 시도했다. 단순하게 반복문을 돌리고, 그 안에 제어문 하나를 통해 언제든지 빠져나올 수 있게 설계하였다. 당연하게도 숫자가 커짐에 따라서 프로그램은 느려졌다. 결국 '시간 초과'라는 결과를 보게 되었다. 시간복잡도를 줄이기 위해 반복문을 쓰지 않고 푸는 방법에 대해 고민하게 되었다.

두번째 시도

#include <iostream>

using namespace std;

int main() {

    // V - A 한 값 goal
    // A - B 한 값 speed
    // 예제 goal / speed
    // 3 / 1
    // 1 / 4
    // 999,999,900 / 1
    // 
    // 기본적으로 나눈 몫 + 1이 답.
    // 단, 나눈 몫이 1 미만인 경우, 2가 답
    // 단, 나눈 몫이 0 이하일 경우, 1이 답.

    long long a, b, v = 0;

    cin >> a >> b >> v;

    long long goal = v - a;
    long long speed = a - b;

    if (goal <= 0) {
        cout << 1 << endl;
    }
    else {
        if (goal / speed >= 1) {
            cout << goal / speed + 1 << endl;
        }
        else {
            cout << 2 << endl;
        }
    }

    return 0;
}

목표량(v)에서 낮에 올라가는 만큼(a) 뺀 값을 goal, a - b는 하루 이동 속도(speed)로 설정하고 돌려보았다. 처음 시도했던 반복문을 이용한 알고리즘은 제한시간을 초과하기 쉬운 로직이므로 제어문을 이용해서 비교연산 정도만 넣어서 구현하고자 했다.
하지만 역시 마음대로 뚝딱뚝딱 되는 것은 없었다. 연산 시간을 줄이기 위해 반복문을 쓰지 않는 접근 자체는 좋았으나, 답을 도출하는 로직에 오류가 있었다. 제출한 이후 틀렸다는 결과를 보고 무엇이 잘못되었는지 판단하기 위해 무작위 예시를 입력하면서 각 부분마다 출력을 하여 디버깅을 해봤다. 기본적인 도출 방법은 어느정도 해결했지만, 나눈 몫에 소수점이 있는 경우를 풀어내지 못하여 틀렸던 것으로 판단했다. 이를 해결한 코드는 다음과 같다.

세번째 시도

#include <iostream>

using namespace std;

int main() {
    // V - A 한 값 goal
    // A - B 한 값 speed
    // 예제 goal / speed
    // 3 / 1
    // 1 / 4
    // 999,999,900 / 1
    // 0 / 5 // A가 너무 커서 한번에 갈 경우
    // 
    // 기본적으로는 v - a / speed + 1가 답
    // v - a / speed 가 딱 안떨어지면 "소수점 올림"

    long long a, b, v = 0;

    cin >> a >> b >> v;

    long long goal = v - a;
    long long speed = a - b;
    long long answer = 0;

    if (goal <= 0) {
        cout << 1 << endl;
    }
    else {
        if (goal % speed == 0) {
            answer = goal / speed;
        }
        else {
            answer = goal / speed + 1;
        }
        cout << answer + 1 << endl;

    }


    return 0;
}

나눈 몫에 소수점이 존재할 경우, 이를 올림 처리하여 몫으로 인식하는 것이 해결방법이었다. 처음으로 "시간 초과"가 떴던 문제를 해결했던 경험이라 풀고 나서 기분이 좋았다.