BOJ-2869 | 달팽이는 올라가고 싶다 c++

✏️ 2869 - 달팽이는 올라가고 싶다
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ math + 시간초과

1. 반복문을 사용해 간단하게 구현
   → 낮에 A만큼 올라간 후 V를 넘어섰는 지 확인 후 밤에 B만큼 내려가기 (반복)
   → V로 입력받을 수 있는 수가 너무 커 반복문으로 구현 시 시간 초과 발생 🥲

while(1)
{
	H += A;    // 낮
    if (H >= V) break;
    H -= B;    // 밤
    day++;
}

2. 수학적 접근 시도
   → 총 걸리는 일수가 x일 때 낮에 +A만큼 밤에 -B만큼 올라갔을 때 막대의 높이와 같거나 커짐

A(x+1) - Bx = V
Ax + A - Bx = V
x(A-B) = V-A
x = (V-A) / (A-B)

→ x가 정확히 나누어 떨어지지 않으면 다음날 낮에 +A만큼 올라가야 정상에 오를 수 있음

풀이

#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))
        day++;

    cout << day;
}