baekjoon #2869_달팽이는 올라가고 싶다_c++

• 처음 작성한 코드 (시간초과 발생)

#include <iostream>
using namespace std;

int main() {
    int A, B, V;
    int day=1;
    cin >> A >> B >> V;
    int x = 0;
    
    while (x < V) {
        x = x + A;

        if (x < V)
            x = x - B;
        else
            break;

        day++;
        
    }
    
    cout << day;

    return 0;
}

=>  이렇게 while문을 사용하면 시간초과가 발생함

 

• 수정 코드

#include <iostream>
using namespace std;

int main() {
    int A, B, V;
    cin >> A >> B >> V;
    int day = 1;

    day += (V - A) / (A - B);

    if ((V - A) % (A - B) == 0) {
        cout << day;
    }
    else {
        day++;
        cout << day;
    }

    return 0;
}

=> while문을 제거하고 식으로 만들어줌

 

V 미터까지 올라가기 위해서는 순간이동을 하지 않는 이상, 시간이 조금이라도 걸리므로 1초도 하루라고 할 수 있음

-> 하루는 무조건 걸리므로 day의 초기값을 1로 정의

day = day + (V - A) / (A - B)

      = 1 + (V - A) / (A - B)

 

• (A - B) * day + A 를 했을 때 V에 도착하면 day를 출력

  -> V = (A - B) * day + A  => 다음 날 아침 안에 V에 도착하면 떨어지지 않으므로, day 만큼 걸림을 알 수 있음

                                    

  -> day = 1 + (V - A) / (A - B)

      day 가 자연수로 딱맞게 떨어지면, V에 도착하기까지 day 만큼 걸림을 알 수 있음  => day 출력

 

• (A - B) * day + A 를 했을 때 V에 도착하지 못하고 V까지 조금 남았다면 다음 날도 올라야 하므로 day + 1을 출력

  -> V = (A - B) * day + A  =>  다음 날 아침 안에 V에 도착하지 못하면,

                                          B만큼 떨어지기도 하고 원래 남은 만큼도 올라야하므로, 다음 날에도 무조건 올라야함

  

  -> day = 1 + (V - A) / (A - B)

      day 가 자연수로 딱맞게 떨어지지 않으면, V에 도착하기까지 day + 1 만큼 걸림을 알 수 있음  => day + 1 출력

 

=> 결국 day가 자연수 일 때 day 를 출력, 자연수가 아닐 때 day + 1을 출력 하면 됨

 

day = 1 + (V - A) / (A - B) 이므로 day 가 자연수인지 아닌지 알기 위해,

위의 식을 계산해서 나머지가 0이면 몫이 자연수로 떨어지는 것이고, 나머지가 0이 아니면 몫이 자연수가 아닌 것임

그러므로, (V - A) % (A - B) 를 수행하여 나머지의 유무를 알아내야 함

 

ex) 2 1 5

A = 2, B = 1, V = 5

day = 1 + (5 - 2) / (2 - 1) = 1 + 3 / 1 = 1 + 3 = 4

=> 4 출력

 

ex) 5 1 6

A = 5, B = 1, V = 6

day = 1 + (6 - 5) / (5 - 1) = 1 + 1 / 4 = 1 + 0 = 1

day + 1 출력 => 1 + 1 = 2

=> 2 출력