[C] 백준 2869번: 달팽이는 올라가고 싶다

 수학적 지식이 필요한 문제이다. 이분 탐색법으로도 풀 수 있지만 항상 더 짧고 간단하게 끝내는 것이 좋지 않은가? 그래서 한 줄 짜리 수식 하나로 끝냈다. 시간 제한을 보면 알 수 있듯이 상수시간, O(1) 내로 풀어야한다. 그래서 선택할 수 있는 방법이 한 줄 수식과 이분 탐색 밖에 없는 것이다. 아마 반복문을 쓰면 백퍼센트 시간 초과가 뜰 것이다.

 

 

입출력 예시

입력	출력
2 1 5	4

입력	출력
10 3 54	8

정답 코드

#include <stdio.h>


int main() {

	int A, B, V;
	int day;

	scanf("%d %d %d", &A, &B, &V);

	day = (V - B - 1) / (A - B) + 1;

	printf("%d", day);


	return 0;

}

코드 설명

1. A, B, V를 입력받는다. 

2. 수식을 설명 하자면, 달팽이는 하루에 (A - B) 미터 씩 총 V미터를 올라가면 된다. 하지만 달팽이가 목표 지점에 도달한 날에는 미끄러지는 것을 감안하면 안되니 총 (V - B)미터를 올라가게 되는 것과 같다. 만약 (V - B)가 (A - B)로 딱 나눠 떨어지지 않으면 몫에 + 1 한 것이 정답이다 (하루 더 가니까). 근데 int형 이라서 나눠 떨어지는지 구분하기 귀찮으니까 (V -B)에 1을 미리 빼놓고 몫에 무조건 1을 더하는 것으로 처리한다.