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

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

예제 입력

2 1 5

예제 출력

풀이에 사용할 알고리즘 구상

문제 자체는 어렵지 않은데, 왜 정답률이 20%대일까? 비밀은 시간 제한에 있다. 시간 제한이 없다면 누구든지 맞출 수 있을 만한 문제지만 문제에서 주어진 변수들의 최댓값이 10억인데 시간 제한이 0.15초이기 때문에 평범한 반복문을 하나라도 만들 경우 무조건 시간이 초과된다. 따라서 이 문제는 가장 적절한 알고리즘을 찾아야 정답을 맞출 수 있다. 나는 이분 탐색을 통해 이 문제를 풀었다.

사실 이분 탐색을 사용해야 한다는 것을 알게 된 순간 이 문제는 그다지 어려운 문제가 아니다. 오히려 이분 탐색의 입문용으로 좋을 정도로 쉬운 문제다. 아직 이분 탐색 알고리즘을 사용하는 문제를 포스팅한 적이 없으니 쉬운 문제가 포스팅하기도 적절하다고 생각돼서 이 문제를 풀게 됐다.

문제에 이분 탐색 알고리즘을 적용해야 한다는 아이디어를 떠올린 다음에 추가로 주의해야 할 사항이 있다면, 연산할 때 달팽이가 매일 (A-B)미터만큼 올라간다고 생각하면 안 된다는 점이다. 왜냐하면 낮에 A미터를 올라갔을 때 나무 막대 꼭대기에 도착하는데 성공한 경우, 밤에 잠을 잘 때 B미터를 미끄러져 내려가는 일이 없기 때문이다. 따라서 매일 (A-B)미터만큼 올라가되, A미터만큼 더 올라갔을 때 나무 막대 꼭대기에 도착할 수 있는 날짜를 구해야 한다.

제출 코드

#include <iostream>

using namespace std;

int A, B, V;
long long cnt = 0;

bool wee(int mid){
        if ((mid-1)*(A-B)+A>=V) return true;
        else return false;
}

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
        cin >> A >> B >> V;
        long long high = V;
        long long low = 1;
        while (low <= high) {
                long long mid = (high + low) / 2;
                if (wee(mid)){
                        high = mid - 1;
                        cnt = mid;
                } else{
                        low = mid + 1;  
                }
        }
        cout << cnt;
        return 0;
}

이분 탐색 문제 풀기

이분 탐색 알고리즘은 문제에서 원하는 정답이 있을 수 있는 범위를 줄여가며 정답을 찾는 알고리즘이다. 범위를 반으로 나누고, 범위 A에 정답이 있다면 다시 범위 A를 반으로 나누고, 범위 B에 정답이 있다면 다시 범위 B를 반으로 나누는 과정을 반복하다 보면 결국 정답이 나오게 된다. 범위 내의 모든 경우에 대해 탐색하는 것보다 훨씬 빠르게 문제를 풀 수 있다. (이 문제로 예를 들면, 일반적은 반복문은 정답을 찾기 위해 최대 10억 번 탐색하게 되는데, 이분 탐색을 사용하면 최대 30번 탐색하게 된다.)

이분 탐색 문제를 풀 때, 무조건은 아니지만 어느 정도 다음과 같은 가이드라인을 따라서 풀면 쉽게 풀 수 있다. 먼저 최종적으로 출력할 변수 하나를 전역 변수(제출 코드에선 cnt)로 선언해 주자. 그 다음 문제에서 주어진 조건(이 문제에선 달팽이가 막대기 끝에 도달하는 조건)을 만족하는 경우 true를 반환하고 아닐 경우 false를 반환하는 함수를 만든다. main 함수 내부에 low와 high를 선언해주고, 각각 cnt가 가능한 범위의 최솟값과 최댓값으로 초기화해준다. 그리고 반복문을 하나 만들어주자. 반복문 안에는 low와 high의 중간값 mid라는 변수를 만들고, 위에서 만든 bool 타입 함수에 mid를 넣었을 때 참이라면 high를 mid보다 작게 만들고, 거짓이라면 low를 mid보다 크게 만들며 이 과정을 low가 high보다 커질 때까지 반복한다. 또한 high를 갱신할 때마다 cnt값도 mid로 갱신해준다.

이 알고리즘이 이분 탐색 알고리즘의 기본 형태다. 이 형태를 따르면 간단한 수준의 이분 탐색 문제는 쉽게 풀 수 있다. 더 어려운 이분 탐색 문제는 이 형태를 문제에서 요구하는 대로 이곳 저곳 튜닝해서 풀면 된다.

회고

문제를 다 푼 뒤 다른 사람들의 풀이를 구글링해보니 이분 탐색보다도 훨씬 더 간단한 풀이법이 있었다. 백준에서 이 문제 분류가 이분 탐색, 수학이길래 수학적으로 쉽게 푸는 방법이 있나 고민했는데, 정말 있었다. 코드가 얼마나 간단하던지 무려 if문 한 개만 쓰고 끝난다. 입출력 부분을 제외하면 5줄도 안 된다. 뒤통수 거하게 맞은 기분이 들었다. 아래 링크를 확인해보자.

참고하면 좋은 링크

수학으로 푸는 방법

문제

입력

출력