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

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

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

오랜만에 머리쓰는 문제를 풀었습니다.

 

이분 탐색 문제인데.. 사실 처음엔 이 문제보고 어떻게 이분 탐색이지 고민을 좀 했었습니다. 사실 범위 보고 이분 탐색을 써야겠다는 생각이 들 수도 있겠죠? (최대 1,000,000,000 이었으니 ㄷㄷ)

고민...

다행히 예전에 풀었던 출입국 심사(SW Expert Academy) 문제를 더듬어 보니까 좀 알겠더라고요?

 

주어진 변수에 집중하기 보다는 출력할 정답에 집중을 하면 해법이 보입니다.

 

결국 달팽이는 시간이 얼마가 되었건 꼭대기에 오르게 되어 있습니다. 그렇다면 정답의 범위를 줄여나가면 어떨까요?

 

정답이 될 수 있는 범위가 하루, 이틀, 3일, 4일, 5일, 6일이라고 정해놓고 시작해봅시다.

 

만약 3일이 정답이 될 수 없다면, 하루, 이틀 모두 정답이 될 수 없습니다. 만약, 4일이 된다면 5일, 6일을 볼 필요가 없겠죠. (저희는 최소값을 찾는거니까요)

이분 탐색과 순차적 탐색 비교

 

이런 식으로 이분탐색을 해나가면 됩니다. 만약, 순차적 탐색을 했다면 범위가 1,000,000,000이기 때문에 100% 시간 초과 뜹니다.

 

다만, 저희는 한 가지 더 고려해야할 부분이 있습니다.

 

재귀함수를 짜다보면 정답이 안되지만, 함수 호출이 되는 경우가 발생합니다.

 

예를들어 4일이 되지만, 3일이 되나 안되나 확인하는 함수 호출이 발생한다는 것입니다. 저는 전역으로 변수를 처리했기에 이 3일의 값이 정답이 아니더라도 저장이 되어버리는 불상사가 발생했습니다.

 

따라서, 정답이 될 수 있는지 없는지의 함수 호출의 값의 범위를 이분화하면서 정답이 될 수 있는 가능성이 있을 때만 그 값을 정답 변수에 넣었습니다.

무슨 소리인지 모르시겠죠? 저도 그렇습니다.

 

코드로 살펴보시죠.

 

#include <stdio.h>

long long A, B, V;
long long y1, y2, mid = 0, result = 0;

void binarySearch(long long left, long long right) {
	if (left <= right) {
		mid = (left + right) / 2;
		y2 = mid * (A - B);
		y1 = y2 + B;
		if (y1 < V) {
			binarySearch(mid+ 1, right);
		}
		else {
			result = mid; // 제가 앞서 말한 정답이 될 가능성이 있는 mid 값만 result에 넣습니다.
			binarySearch(left, mid - 1);
		}
	}
}

int main(void) {
	scanf("%lld %lld %lld", &A, &B, &V);
	long long left, right;
	left = 1; right = (V / (A - B)) + 1;
	binarySearch(left, right);
	printf("%lld", result);
}

주석 처리한 곳이 아까 제가 설명한 부분입니다.

 

무조건 정답이 될 수 있는 mid 값만 result에 넣어가면서 달팽이가 움직여야하는 최소한의 일 수를 구할 수 있었습니다.

 

이분 탐색 개념을 알아가는데 좋은 문제라고 생각합니다.

---

이상 2869 - 달팽이는 올라가고 싶다 (이분 탐색)였습니다. ^_^