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

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

처음 제출 코드

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a, b, v, sum, day = 0;
    cin >> a >> b >> v;
    while(true)
    {
        sum += a;
        day++;
        if (sum >= v) break;
        sum -= b;
    }
    cout << day;
}

그냥 정말 단순하게 반복문으로 작성한 코드는 (당연하게도) 시간 초과가 되었다

 

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a, b, v, day = 1;
    cin >> a >> b >> v;

    day += (v - a) / (a - b);
    if ((v - a) % (a - b) != 0) day++;

    cout << day;
}

수식으로 푼 코드

 

사실 굳이 a를 더했다가 b를 빼는 식으로 하지 않고도 a - b를 계속 더해줘도 된다

단, 단순히 a - b값만 계속 더하게 되면 정상에 올라간 후에는 미끄러지지 않는다는 조건을 만족시킬 수 없다

 

따라서 v - a까지만 a - b를 더해준다면, 하루 후에 무조건 달팽이는 정상에 도달할 수 있다

 

이를 반복문으로 처리하면 위 결과와 똑같아지므로 (v - a) / (a - b)의 값을 day에 더해준다

 

이때 int 끼리의 나눗셈은 몫을 내림하기 때문에, 나머지가 0이 아닌 경우 하루를 더 올라가야 남은 거리가 a보다 작아지므로 mod 연산으로 체크해주었다