문제 정보

백준 ( BOJ ) 2869 달팽이는 올라가고 싶다

문제 풀이 : 수학, 이분 탐색

문제 출처 : https://www.acmicpc.net/problem/

시작 Thinking

우선, 수학적으로 계산하면 가장 쉽다..

위를 보면, (a-b)* x 가 (v - a ) 보다 크게 되는 순간, 그 다음날이 문제의 정답이 된다.

즉,

(a-b)* x  > ( v - a ) 
-> x > ( v- a ) /( a - b)

이렇게 된다.

다만 여기서, 주의 해야 할 점은,

우리 계산은 int로 하니까,

나머지 까지 생각 해 줘야 한다.

나머지가 남으면, 하루 더 걸리는 것만 생각 하면 쉽다.

그러나 원래 이 문제의 의도는 수학이 아니라, 이분 탐색을 하는 문제이니까

이분탐색 방법도 설명 드리겠습니다.

우선 left, right, middle 을 정합니다.

left는 뭘까요? 최소값은, 높이 / 하루에 올라 갈 수 있는 수 로 설정 해 주면

될 거 같네요.

right는 계산이 복잡하니, 그냥 높이 그대로 두고 가겠습니다.

middle 은 항상 (left + right ) / 2 입니다.

그리하여 middle이 결과값에 부합하는지 확인 합니다.

부합 한다면, 상한선을 middle로 떙겨 옵니다.

그리고, middle을 다시 (left+right)/2 로 해 주면 됩니다.

만약 부합하지 않는다면, 하한선을 middle로 땡겨 오고

middle 을 다시 설정 해 주면 됩니다.

이렇게 하면, 되는구간 vs 안되는 구간을 점점 좁혀나가게 되며,

결과적으로 middle 이 left나 right 와 같아지는 순간 정답이 되게 됩니다.

코드

#include <iostream>

using namespace std;


int main() {
	int a, b, v;
	int lower, upper, middle;
	int result;
	cin >> a >> b >> v; 

	// --- 수학적 접근 시작
	result = (v-a)/ (a - b)+1;
	if ((v - a) % (a - b) != 0)
		result++;
	cout << result << endl;
	// --- 수학적 접근 끝. 
  
  // 이분탐색 시작
	lower = (v / a);
	upper = v;
	middle = (lower + upper) / 2;

	while (true) {
		if ((a - b)*(middle - 1) + a < v) {
			lower = middle;
			middle = (lower + upper) / 2;
		}
		else {
			upper = middle;
			middle = (lower + upper) / 2;
		}
		if ((upper == middle) || (lower == middle)) {
			if ((a - b) * (middle - 1) + a >= v) {
				cout << middle;
			}
			else
				cout << middle + 1 ;
			break;
		}
	}
  // 이분탐색 끝
	return 0;
}

후기

• 소요 시간 : 5분(수학적), 15분(이분탐색)