[이분 탐색 01]

#include <stdio.h>
using namespace std;

int A, B, V;
int minn = 1000;
int ansDay = 0;
int dayHeight(int day){
	int yesterdayHeight = (A - B) * (day - 1);
	int todayHeight = yesterdayHeight + A;
	// int tomorrowHeight = tdayHeight - B;
	return todayHeight;
}

int main()
{
	scanf_s("%d %d %d", &A, &B, &V);
	int right = V + 1;	// <쌉가능>
	int left = 0;	// <불가능>
	//printf("left,right : %d,%d\n", left, right);

	int result = right;
	
	while (left <= right) {
		int mid = (left + right) / 2;
		int dailyMax = dayHeight(mid);
		//printf("mid:%d , dM:%d\n", mid, dailyMax);
		if (dailyMax >= V) {
			result = result < mid ? result : mid;
			right = mid - 1;
		}
		else if (dailyMax < V) {
			left = mid + 1;
		}
	}
	printf("%d", result);
}

 

평소 사용하는 분할정복이랑 개념이 같음.

 

1. log(n) 이라 슈퍼빠르다.

2. 초기 left, right 잡을땐 최악, 최고일 경우의 수를 적는게 맞다.

3. left == mid 는 서칭이 끝났다는거지, best case 를 찾았다는게 아님.

4. 딱뎀일때 break 고려해도될것같은데?

 

팁 > 이분탐색 쓰려면 위에 식 그냥 외우고,

문제마다 이분탐색 적용할 각을 잘재(습득하)면 됨