문제

문제 링크

어떻게 접근할 것인가

  • 달팽이가 정상에 올라가는데 걸리는 날의 최솟값을 구하는 문제이다.
  • 즉, 날짜의 lower_bound를 찾는 문제이다.
  • 여기서 주의할 점은 달팽이의 위치는 하루 전날까지는 올라간 높이 빼기 내려간 높이이지만 당일은 올라간 높이만이다.
  • 그래서 이분 탐색을 이용해서 정상에 도착하지 못하는 애들의 upper_bound를 찾아주고 이를 + 1 해준 값을 출력한다.(이것이 lower_bound와 동일하다.)
  • 코드 상에서는 계속해서 정상에 도착하지 못할 마다 정답 값을 업데이트 하도록 하였다.

코드

#include <cstdio>

int main(){
    int v, a, b;
    scanf("%d %d %d", &a, &b, &v);
    int d = a - b, l = 1, r = v, ans = 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(v <= (long long)((mid - 1) * d + a)) r = mid - 1;    
        else l = mid + 1, ans = mid + 1;
    }
    printf("%d", ans);
}

느낀점

  • upper_bound와 lower_bound 값을 구하기 위해서 ans 값을 업데이트 하는 지점이 무척 헷갈린다.
  • 좀 더 문제를 풀어보면서 헷갈리지 않도록 연습해봐야겠다!