BOJ [11561] 징검다리

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

1. 분류

이분탐색

2. 풀이

최대로 밟을 수 있는 징검다리의 개수를 구하는 문제이다.

1~N까지의 징검다리가 있는데, 어디서 시작하던지는 상관 없다.

단, 다음 단계는 이전 단계보다 무조건 1개 이상 더 멀리 뛰어야 하며 N번째 징검다리는 반드시 밟아야 한다.

이 때 최대로 밟을 수 있는 개수는 무조건 첫 번째 징검다리부터 시작하는 것이다.

앞에서부터 1, 2, 3, ..., N항이라고 할 때 어짜피 이전 단계보다 1 이상만 더 멀리 뛰면 되기 때문에 N-1항과 N항의 거리는 상관 없고

1, 3, 6, 10, 15, ..., N 순서대로 뛰면 최대 개수가 될 것이다.

시작 항이 1인 등차수열의 공식 N * (N-1) / 2에 적합한 N값을 이분 탐색으로 찾아내면 끝이다.

---

3. 소스코드

#include <cstdio>
typedef unsigned long long ll;

ll chk(ll x)
{
	return x * (x + 1LL);
}

int main()
{
	int t;
	for (scanf("%d", &t); t > 0; t--)
	{
		ll n;
		scanf("%llu", &n);

		ll low = 1LL, high = n, mid = 1LL;

		while (low <= high)
		{
			mid = (low + high) / 2LL;

			if (chk(mid) > n * 2)
				high = mid - 1LL;
			else
				low = mid + 1LL;
		}

		if (chk(mid) > n * 2)	mid--;

		printf("%llu\n", mid);
	}

	return 0;
}