취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18324번 문제인 Race이다.
문제는 아래 링크를 확인하자.

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

BOJ#1011의 아이디어를 응용하여 해결할 수 있는 문제이다.

이동하는 데에 사용할 시간을 T라고 하자.

T가 커질 수록 그 시간동안 이동할 수 있는 총 거리는 증가하므로, 가능한 전체 시간의 범위를 두고 이진탐색(binary search)를 통해 T를 찾는 방법을 시도할 수 있다.

다만 T를 직접 변수로 이용하면 식을 세우기 쉽지 않으므로, 글쓴이는 "도달한 최고 속도"를 기준으로 그 때 이동할 수 있는 거리를 구해 이진탐색을 진행했다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll dist, Q; cin >> dist >> Q;
	while (Q--) {
		ll K; cin >> K;
		if (K * (K + 1) / 2 >= dist) {
			ll L = 1, R = K;
			while (L < R) {
				ll mid = (L + R) / 2;
				if (mid * (mid + 1) / 2 >= dist) R = mid;
				else L = mid + 1;
			}
			cout << L << '\n';
		}
		else {
			ll KK = K * (K - 1) / 2;
			ll L = K, R = 100000;
			while (L < R) {
				ll mid = (L + R) / 2;
				if (mid * mid - KK >= dist) R = mid;
				else L = mid + 1;
			}
			if (L * (L - 1) - KK >= dist) cout << 2 * L - K - 1 << '\n';
			else cout << 2 * L - K << '\n';
		}
	}
}