문제

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

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

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

입력

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

출력

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

예제

예제 입력
2 1 5

예제 출력
4

접근

  • 예전에 한 번 풀었던 문제이다. 처음 풀었을 때 수학적 접근으로 풀었으나 이분탐색을 다시 공부하기 위해 이분탐색으로 접근해본다.

내가 생각한 풀이

  • 달팽이가 한 번 올라가고 한 번 내려오는 걸 생각한다. 나는 올라가야 하는 거리에서 한 번 덜 올라간 거리, 즉 V-A를 이분 탐색으로 찾은 후 1을 더하여 정답을 출력할 것이다.

미처 생각하지 못했던것

  • 아무 생각 없이 right의 초기값을 1000000000으로 설정했다가 overflow가 나버렸다…ㅎ

코드

#include<iostream>
using namespace std;

int main(void)
{
  int A, B, V, left = 0, right, result = 0;
  cin>>A>>B>>V;
  right = V + 1;
  while(left <= right)
  {
    int mid = (left + right)/2;
    if(mid * (A - B) > V - A){
      right = mid - 1;
      result = mid;
    }
    else if(mid * (A - B) < V - A){
      left = mid + 1;
    }
    else
    {
      result = mid;
      break;
    }
  }
  cout<<result + 1;
  return 0;
}

코드2

#include<iostream>
using namespace std;

int main(void)
{
  int A, B, V, left = 0, right, result = 0;
  cin>>A>>B>>V;
  right = V + 1;
  while(left <= right)
  {
    int mid = (left + right)/2;
    if(mid * (A - B) > V - B){
      right = mid - 1;
      result = mid;
    }
    else if(mid * (A - B) < V - B){
      left = mid + 1;
    }
    else
    {
      result = mid;
      break;
    }
  }
  cout<<result;
  return 0;
}

생각해볼 점

  • 2개의 코드가 있다. 하나는 조건이 mid * (A - B) > V - A이고 다른 하나는 mid * (A - B) > V - B이다. 또다른 차이점으로는 result에 1을 더해주는 것과 그렇지 않은 것이다. 결론적으로 둘 다 정답 처리가 된다. 내가 생각하기엔 첫 번째 코드가 맞는 것 같은데 두 번째 코드도 맞는 이유가 사실 정확하게 머리에 안 들어온다.. 대충 생각하기로는 올라가는 거리가 항상 내려오는 거리보다 커서 두 번째 코드도 조건을 만족시키는 것 같다..!