[분할 정복] BOJ 2869 달팽이는 올라가고 싶다

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

이 문제를 처음에 풀 때는 간단하게 while문을 이용해 풀려고 했지만, 시간초과가 나는 것이다.

 

#include <iostream>
using namespace std;

int main() {
	int a, b, v, sum = 0, cnt = 0;
	cin >> a >> b >> v;
	while (true) {
		cnt++;
		sum += a;
		if (sum >= v) break;
		sum -= b;
	}
	cout << cnt;
}

시간 초과 코드

 

하지만, (1 ≤ B < A ≤ V ≤ 1,000,000,000) 조건에 가장 큰 숫자가 무려 10억인 것을 보고 시간 제한이 0.15초인 이 문제에서는 저 코드는 택도 없을 게 뻔했다. 

 

그래서 이분 탐색 알고리즘을 이용해서 풀기로 했다.

#include <iostream>
using namespace std;

int main() {
	long long a, b, v;
	cin >> a >> b >> v;
	int right = 1000000000;
	int left = 0;
	int mid;
	while (left <= right) {
		mid = (right + left) / 2;
		long long result = (a - b) * mid + a;
		long long r = (a - b)*(mid - 1) + a;
		if (result < v) left = mid + 1;
		else if (result >= v && r < v) {
			cout << mid + 1;
			break;
		}
		else right = mid - 1;
	}
}

이분 탐색 코드

 

이런 식으로 코드를 구현하면 무려 코드가 log 스케일로 시간이 감소하게 된다.

코드에서 result와 r이 있는데 V의 값이 result가 V값보다 클 수도 있기 때문에 저런 식으로 mid값이 하나 작은 r을

만들어서 범위를 나눠서 값을 구했다.