[BOJ 2869] 달팽이는 올라가고 싶다 - 수학

문제 링크

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

문제 요약

달팽이가 높이 V미터인 나무 막대를 올라간다. 낮에 A미터 올라가고 밤에 B미터 미끄러지며, 정상에 도달하면 더 이상 미끄러지지 않는다. 며칠이 걸리는지 계산하는 문제.

접근 방법

• 자료구조: 변수만 사용
• 알고리즘: 수학적 계산 (나눗셈과 나머지 연산)
• 핵심 아이디어:
  • 마지막 날에는 정상에 도달하면 미끄러지지 않으므로, 마지막 날 전까지만 (A-B)씩 올라간다고 생각
  • (V-A) 높이까지 올라가는데 필요한 날짜를 구하고, 마지막 날 하루를 추가
  • (V-A)를 (A-B)로 나눈 몫에 나머지가 있으면 +1, 그리고 마지막 날 +1

풀이 코드

#include <iostream>

int main() {
    long long A, B, V;
    std::cin >> A >> B >> V;

    long long days = (V - A) / (A - B);
    if ((V - A) % (A - B) != 0) {
        days++;
    }
    days++;

    std::cout << days << std::endl;

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

참고한 풀이

• 반복문으로 하루씩 시뮬레이션하면 시간 초과가 발생 (V는 최대 10억)
• 수학적으로 계산하여 O(1)에 해결해야 함