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

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

처음에는 이 문제를 시뮬레이션 해가며 답을 구하려고 했다. 아래처럼.

#include <cstdio>

using namespace std;

int main()
{
	long long A, B, V;
	scanf("%lld %lld %lld", &A, &B, &V);
	long long day = 1;
	long long H = 0;
	while (true) {
		H += A;
		if (H >= V)
			break;
		H -= B;
		day++;
	}
	printf("%lld\n", day);
	return 0;
}

그러나 입력이 최대 10억까지 주어지고, 시간제한이 0.15초이므로 위의 코드는 시간초과가 발생한다.

그래서 식을 생각해야 하는데, 처음 생각해낸게 다음과 같다.

(N - 1) (A - B) + A ≥ V

위에서 N은 나무 막대를 모두 올라가는데 걸린 일수이다.

N - 1일까지는 A 만큼 올라갔다가 B 만큼 내려오다가, N일(마지막날)에는 A 만큼 올라가고 끝이다.

이걸 베이스로 N을 구하는 방법을 생각해보자...

(V - A) / (A - B) 가 나누어 떨어지면 A 만큼 더 올라갔을 때, V에 도달한다.

이 경우에는 그 몫에 1을 더한 값이 N이 된다.

만약 나머지가 생기면, 그 나머지는 (A - B)보다 작으며, 남은 거리는 (A - B) + A보다 작으므로,

이 경우에는 그 몫에 2를 더한 값이 N이 된다.

A와 V가 같을 경우, N이 0이 되는데, 이 떄는 N을 1로 만들어준다.

#include <cstdio>

using namespace std;

int main()
{
	long long A, B, V;
	scanf("%lld %lld %lld", &A, &B, &V);
	long long int N = (V - A) / (A - B);
	if ((V - A) % (A - B) == 0) {
		N++;
	}
	else {
		N += 2;
	}
	if (N == 0)
		N = 1;
	printf("%lld\n", N);
	return 0;
}