무지개 달팽이

Q. 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력.

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

이분 탐색 관련 문제를 풀어보고 싶어서 선택한 문제이다.

현재까지 공부한 바로는 이분 탐색을 하기 위해서는 기준 배열이 나오는 것으로 알고 있는데, 이 문제에서는 찾을 수 없었다. 그래서 여러 블로그에서 문제 풀이를 살펴 보았다.

"( 나무의 길이(v) - 낮에 올라가는 거리(a) ) 에서 하루에 올라가는 거리(a - b)를 나누고

나누어 떨어지면 그 몫을 날 수(n)에 더하고, 떨어지지 않으면 여기에 +1을 하여 더한다."

즉, 이분 탐색으로 풀기 보다 수학 문제처럼 접근하는 것이 좋다는 것이다.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int v, a, b;
	int n = 1;

	scanf("%d", &a); scanf("%d", &b); scanf("%d", &v);

	int temp = (v - a) / (a - b);

	if ((v - a) % (a - b) == 0)
		n += temp;
	else
		n += (temp + 1);

	printf("%d", n);

	return 0;
}