[백준 C++] 31498 장난을 잘 치는 토카 양 - 이분탐색

31498번: 장난을 잘 치는 토카 양

#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	ll A, B, C, D, K;
	cin >> A >> B >> C >> D >> K;

	ll End = ceil(double(A + C) / D);

	ll S = 1;
	ll E = End;
	ll Catch = End;
	ll Arrive = End + 1;
	while (S <= E)
	{
		ll T = (S + E) / 2;
		if (B - K * (T - 1) <= 0)
		{
			E = T - 1;
			continue;
		}

		ll Toca = A - (T * (2 * B - K * (T - 1)) / 2);
		ll Doldol = A + C - T * D;
		if (Toca <= 0)
		{
			Arrive = min(Arrive, T);
			E = T - 1;
		}
		else
		{
			if (Toca >= Doldol)
			{
				Catch = min(Catch, T);
			}
			S = T + 1;
		}
	}

	if (Arrive < Catch)
	{
		cout << Arrive;
	}
	else
	{
		cout << -1;
	}
}

---

 

등차수열의 합 & 이분탐색을 이용해서 푸는 문제입니다.

돌돌이가 집에 도착하는 시간, 토카가 집에 도착하는 시간, 토카가 돌돌이에게 잡히는 시간을 구하고

해당 시간들을 비교해서 답을 출력해주면 됩니다.

 

돌돌이는 같은 속도로 이동하기 때문에 집에 도착하는 시간을 쉽게 구할 수 있지만,

토카는 이동속도가 매 초마다 (일정하게) 변하기 때문에

등차수열의 합 공식을 이용해서 몇 초에 집에 도착하는 지를 탐색해야 합니다.
이 때 입력 범위가 10^12로 매우 크기 때문에 이분 탐색을 이용해서 시간복잡도를 최소화합니다.

 

탐색 시에는 토카의 이동속도가 0이하가 될 경우는 제외해주어야 합니다.

그리고 이분탐색을 통해서 토카가 집에 도착하는 시간과 돌돌이에게 잡히는 시간을 찾아줍니다.