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

문제

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

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

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

시간제한 : 0.15 초 (추가 시간 없음) 

입력

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

출력

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int a, b, v, day;


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

	if ((v-a) % (a-b) == 0) 
	{
		day = (v - a) / (a - b) + 1;
	}
	else {
		day = (v - a) / (a - b) + 2;
	}
	
	printf("%d", day);
}

 

 

문제풀이

처음에 조건문을 한 번 써서 풀이를 했으나, 시간초과로 fail했습니다.

문제는 0.15초 시간 제한을 얘기하고 있고, 이는 `상수시간 O(1)` 로 제한을 두라는 것이었습니다.

따라서 조건문을 포기해야했고, 출력할 DAY를 방정식으로만 나타내어야 했습니다.

 

정상에 도착하는 마지막 날은 내려오지 않고, 올라가는 A만 고려하면 되기때문에 (V - A)를 올라갈 거리로 잡고, DAY에 1을 더해줬습니다. (마지막 날을 미리 1로 빼둔 것)

이제 (V - A) 에서 하루마다 올라가게 되는 (A - B)를 나눠주고 아까 1을 더해주면 DAY가 되겠습니다.

• 나머지가 0일 때        : `(V - A) / (A - B) + 1`
• 나머지가 0이 아닐 때: `(V - A) / (A - B) + 2`

나머지가 0이 아닐 때는 나머지만큼 올라가기 위해 하루를 더해줘야 하기 때문입니다.

 

 

비고

수학적 센스가 요구되는 문제였습니다. 그리디하다고 볼 수 있습니다.