[BaekJoon 2869][🟤1] 달팽이는 올라가고 싶다

❓ 문제

백준 2869 - “달팽이는 올라가고 싶다”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (수학)

- 알고리즘

• Mathematics

- 설명

간단한 규칙을 사용해 수학적으로 푸는 방법이다.

처음에는 단순하게 while 반복문을 사용해서 매일마다 올라가고 내려가는 것을 반복해 최종 일수를 구하는 방법으로 풀려고 했다.

그러나 그럴 경우 시간 제한이 0.25초이므로 최대 반복수는 2500만회 정도인데 비해 입력값의 조건 범위가 1 <= B <= A <= V <= 10억이므로, 최악의 경우 10억회를 반복해야 하는 매우 비효율적인 풀이였다.

따라서 어떠한 '규칙'을 가지고 푸는 것임을 깨달았다.

규칙은 매우 간단하다.

1. 마지막 날에는 A만큼 오르는 것만 생각하면 되므로 전체 길이를 V - A로 잡는다.
2. 마지막 날을 제외한 모든 날은 A - B만큼 오른다.
3. 따라서 전체 길이를 매일 오르는 길이로 나눠주면 된다.
4. 이 때, 올림 나눗셈 기법을 사용하면 (V - A + A - B - 1) / (A - B) 이 된다.
5. 시작하는 날이 1일이기 때문에 마지막에 1을 더해주면 끝이다.

나의 비효율적인 풀이는 O(N)이지만, 이 방법은 수학적인 계산이므로 O(1)이다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iA{}, iB{}, iV{};
    cin >> iA >> iB >> iV;

    int iGap{ iA - iB };

    // 마지막 날에 iA만큼 올라가는 거 빼고, iGap만큼 매일 올라간다고 생각하고 올림 나눗셈 사용 (첫날이 1일이므로 마지막에 1 더하기 필수)
    cout << (iV - iA + iGap - 1) / iGap + 1;

    return 0;
}

---

💭 후기

이 문제를 풀면서 다시 한 번 깨닫게 되는건 '조건'을 잘 생각하자였다. 시간 제한이 되었든, 메모리 제한이 되었든, 실제로 코드를 짜기 전에 한 번 생각해보면 그만큼 시간을 절약할 수 있다.

그리고 올림 나눗셈 같은 수학적 기법도 계속 유용하게 쓸만하니까 잘 기억해두자.

🔗 참고자료

• 산술, 비트 기법