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

2869 달팽이는 올라가고 싶다

시간제한을 못 보고 풀었다가 함정에 빠진 문제이다.

#include	<iostream>
using namespace std;

int a, b, v, ans, cnt;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> a >> b >> v;
	while (ans < v)
	{
		cnt++;
		ans += a;
		if (ans < v)
			ans -= b;
	}
	cout << cnt << endl;
}

처음 식은 다음과 같았다. 그러나 마지막 테케에서 시간이 오래 걸려서 불안하던 와중 시간초과가 떴다 역시ㅎ

반복문을 쓰게되면 v의 수가 크고 a와 b가 작을수록 연산횟수가 늘어나게 된다. 이 문제는 특히나 시간제한이 0.15초로 다른 문제보다 적은 편이기 때문에 다른 방법을 떠올려야 한다.

반복문을 쓰지 않고 연산하기 위해서는 간단한 수학 공식을 세워야 한다.

며칠이 걸리는지 알아야 하므로 (a - b) * N = v - a라고 생각하고 식을 전개했다. v - a가 (a - b) * N 보다 작아지면 그 다음날 달팽이는 나무를 끝까지 오를 수 있게 된다. 이 식을 전개하면 N = v - a / a - b이다.

그런데 연산을 int형으로 하게 되면 나머지 처리에 대한 문제가 생긴다. 나머지가 남는 경우는 하루가 더 걸린다고 생각하면 된다. 나머지가 없을 때는 그냥 출력하면 된다.

처음 문제를 보고 이분탐색을 생각했으나 식 전개에 대한 풀이가 재밌어서 이 방법으로 풀게됐다. 이분탐색도 가능할듯

#include	<iostream>
using namespace std;

int a, b, v, ans;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> a >> b >> v;

    ans = 1;
    ans += (v - a) / (a - b);
    if ((v - a) % (a - b) != 0)
        ans++;
    if (a >= v)
        cout << "1";
    else
        cout << ans;
    return 0;
}