[c++] 백준 2869 달팽이는 올라가고 싶다

백준 단계별로 풀어보기 [기본수학 1] 달팽이는 올라가고 싶다

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

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

 

[풀이]

처음에는 반복식을 이용해서 풀이했다. 입력범위가 커서 시간초과가 걸린다. O(1)의 상수시간 안에 풀어야 하므로 반복문을 이용하지 않고 다시 풀었다.

달팽이는 하루에 a-b 미터 씩 총 v 미터를 올라간다. 그런데 마지막 날에는 b미터만큼 미끄러지지 않으므로 총 v-b미터를 올라간 것과 같다. (v-b) / (a-b) 가 나누어 떨어지지 않으면 하루를 더 가야하므로 몫 + 1이다.

 

[코드] 

-반복문으로 뻘짓

#include <iostream>

int main(void) {
	int a, b, v, day=0, sum=0;
	std::cin >> a;
	std::cin >> b;
	std::cin >> v;
	sum = a - b; day++;
	while (sum < v) {
		sum += a; 
		if (sum >= v) {
			day++;
			break;
		}
		sum -= b;
		day++;
	}

	std::cout << day;

	return 0;
}

-수정본

#include <iostream>

int main(void) {
	int a, b, v, day=0;
	std::cin >> a;
	std::cin >> b;
	std::cin >> v;
	day = (v - b) / (a - b);
	if ((v-b)%(a-b) == 0) std::cout << day;
	else std::cout << day + 1;

	return 0;
}