[백준 / BOJ] - 2869번 달팽이는 올라가고 싶다 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2869] 

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

문제

 

낮에 A미터 올라가고, 밤에는 B 미터 미끄러지는 달팽이가 V미터를 오르는데에 걸리는 일자를 구하는 문제이다.

입력으로는 A,B,V를 입력받고, B는 반드시 A보다 작다.

 

풀이

 

이 문제도 반복문을 통해 높이를 오르려고 할 경우, V의 범위가 최대 1,000,000,000이므로 시간초과가 발생한다.

따라서, 몇일이 걸리는지를 수학적으로 식으로 구현하여야 한다.

 

정상에 일단 다다르기만 하면 미끄러지지는 않으므로, 최종적으로 가야하는 목표는 V가 아닌 V-A까지만 가면 다음날 아침에 A만큼 올라서 정상에 다다를 수 있다.

 

그리고 V-A를 가는데에 걸리는 기간은 (V-A)/(A-B)이다.

이때 (V-A) / (A-B)가 나머지가 0일 경우에는 (V-A) / (A-B) 일 만큼 오르고, 마지막날 A만큼 오르면 되지만,
(V-A) / (A-B)의 나머지가 0이 아닐 경우에는 정상에 도달하기에 이동거리가 조금 모자라므로 1을 추가로 더해주면 된다.

 

 

코드

 

#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)
        day++;
    if(a >= v)
        cout << "1";
    else
        cout << day;
    return 0;
}

 

 

평가

 

반복문을 사용할 경우 무조건 시간초과가 발생하는 문제이다.

목표점이 V가 아닌 V-A라는 것을 캐치하는것이 관건이고, 그 후 (V-A) % (A-B)를 활용하여 1을 더해줄지 안더해줄지를 결정하는 것이 정답으로의 접근 방법이다.

나머지 연산을 고려하지 못하는 경우가 많아 정답률이 27%인 다소 고난도 문제이다.