[ C / C++ ] 백준 11561 징검다리

문제

승택이는 강을 건너려 한다.

승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.

승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.

승택이는 이제 강의 한쪽 변 앞에 서 있다.

강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.

강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.

이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.

물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.

1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
3. N번 징검다리는 반드시 밟아야 한다.
4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.

승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

 

#include <algorithm>
#include <iostream>
#include <vector>
#define MAX 141421357
using namespace std;

long long t, n;
int main(void)
{
	scanf("%lld", &t);

	while (t--)
	{
		scanf("%lld", &n);
		long long l = 1, r = MAX - 1;

		while (l <= r)
		{
			long long mid = (l + r) / 2;
			long long aa = (mid * (mid + 1)) / 2;
			if (aa == n)
			{
				r = mid;
				break;
			}
			if (aa < n)l = mid + 1;
			else r = mid - 1;
		}
		printf("%lld\n", r);
	}
	return 0;
}