백준 2869 달팽이는 올라가고 싶다(이분탐색)

달팽이는 올라가고 싶다

A,B,V 제한을 보면 10억이다. 보기엔 간단히 더해서 풀면 풀릴거같은 문제지만, 그렇게 풀면 O(N)이 되어 시간초과가 된다.

더 적은 시간으로 풀어야 하는데, 이 문제는 두가지 문제풀이가 존재한다.

수학으로 접근하는 방법 O(1) 과 이분탐색으로 접근하는 방법 O(logN) 이다.

나는 이분탐색을 이용해서 풀었고, 수학으로 접근하는 방법을 보고싶다면 다른 블로그를 참고하길 바란다.

주의해야할 점 이분탐색에 대한 개념을 인지하고 있다는 전제 하에 해설합니다! 이분탐색에 대한 개념을 한번 보고 오시면 도움이 많이 될 겁니다!

문제분석

1.낮에 a만큼 올라가고, 밤에 b만큼 내려간다.

• 첫번째 날 +a-b, 두번째 날 +a-b, … , __내가 구하려는 날__에 +a(-b)를 하면 v가 넘는다.

  첫번째 날	두번째 날	...	내가 구하려는 날의 전날	내가 구하려는 날
  X	X	X	X	O

• 어떤 기준에 의해 Yes/No로 나누어지는 것이므로 이분탐색으로 풀 수 있다.

2.어떤 기준인가?

• 기준은 어떤 x날의 전날까지 오른 길이 (x-1) * (a-b) 에 x날의 a를 더한 값 (x-1) * (a-b)+a 이 v보다 크면 뒤의 범위를 앞으로 당겨주면 되고, 작으면 범위를 뒤로 밀어주면 된다.

3.첫날과 마지막날의 범위는 어떻게 잡나?

• 이분탐색에서 중요한 부분중 하나이다. 가능한 정답의 최솟값과 최댓값을 정해주어야 하는데, 이 문제에선 최솟값 : 첫번째 날(1) 이고, 최댓값: a<b이므로 무조건 하루에 하나는 올라간다. 즉 v가 최댓값이 된다.

소스

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	int a, b, v;
	cin >> a >> b >> v;
	long long last = v;
	long long first = 0;
	long long mid;
	long long ans;
	while (first <= last) {
		mid = (first + last) / 2;
		if (v <= (mid-1)*(a-b)+a)
		{
			last=mid-1;
			ans = mid;
		}
		else {
			first=mid+1;
		}
	}
	cout << ans;
}