백준 2869번 - 달팽이는 올라가고 싶다

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

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

우선 처음 고안한 방법은, 반복문을 이용하는 방법이었다.

#include <iostream>
using namespace std;

int main()
{
	int a, b, v;
	cin >> a >> b >> v;

	int day = 0;

	int temp = 0;
	while (true)
	{
		temp = temp + a;
		if (temp >= v)
		{
			day++;
			break;
		}
		else
		{
			temp = temp - b;
			day++;
		}
	}
	cout << day;
	return 0;
}

이러면 정상적으로 코드의 결과값은 나오지만, 시간제한이 있어서 시간 초과로 인해 실패가 뜬다.

반복문을 돌렸기 때문에, 시간 초과가 나온듯 싶어, 수식으로 접근해야한다는 생각이 들었다.

 

우선 사고 과정 그림은 이렇다.

단순히  v / (a-b) 하는 것은 오류이다. 왜냐하면 그냥 v 직전까지 갔다가 +a를 했는데 딱 맞거나 초과해도 day + 1을 할 수 있기 때문이다.

그래서 그 직전을 v -a 로 설정했다.

그리고 나서 (v - a)를 (a - b)로 나누었을 때 나누어떨어진다면, 그 때 + a 를 통해 맞춰주면 되므로, 

day = (v - a) / (a - b) + 1 이다.

만약 나누어 떨어지지 않는다면, 그 직전보다 아래에 있다는 소리 이므로, (a - b) 칸 한 번 가고 나서, + a를 하면 초과하는 것이기에, day는

day = (v - a) / (a - b) + 2 가 된다.

#include <iostream>
using namespace std;

int main()
{
	int a, b, v;
	cin >> a >> b >> v;

	int size = a - b;
	int temp = v - a;
	int day;

	if (temp % size == 0)
		day = temp / size + 1;
	else
		day = temp / size + 2;

	cout << day;

	return 0;
}