백준 2869 (달팽이는 올라가고 싶다) c++

문제

2869번: 달팽이는 올라가고 싶다

달팽이는 낮에 a 만큼 올라가고 밤에 b만큼 내려옵니다. 

정상의 높이가 v라고 할때 달팽이는 며칠만에 정상에 도착하는지 구하는 문제입니다.

달팽이가 최초로 정상에 올라간 후에는 미끄러지지 않습니다.

 

처음에는 단순히 반복문을 돌려 계산 했지만 

시간 초과가 나왔습니다.

 

따라서 시간제한이 0.15초 이기 때문에 O(1)의 시간 복잡도를 가져야 합니다.

 

우리는 최초로 정상에 도착하면 다시 미끄러지지 않기 때문에 미리 빼줄 수 있습니다.  => v - b

또한 우리는 하루에 (a-b) 만큼 이동할 수 있습니다.

식을 세워 보면 

(a - b)x = (v - b)

x = (v - b) / (a - b)가 됩니다.

 

예제(1)를 대입해 보면 

a = 2, b = 1, v = 5 

4 / 1 = 4

정답

 

예제(2)를 대입해 보면

a = 5, b = 1, v = 6

5 / 4 = 1

정답은 2인데 1이 나옵니다...

(v-b)가 (a-b)로 나누어 떨어지면 그대로 쓰면 되지만 나누어 떨어지지 않는다면 +1을 해줘야 합니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int a, b, v;
    cin >> a >> b >> v;
 
    int cnt;
 
    if ((v - b) % (a - b) == 0)
        cnt = (v - b) / (a - b);
    else cnt = (v - b) / (a - b) + 1;
    
    cout << cnt;
    
 
    
    return 0;
}