[ boj : 11561 ] 징검다리

www.acmicpc.net/problem/11561

11561번: 징검다리

문제 : 징검다리를 건너기 위해 점프를 하는데  x 칸을 점프했으면 다음에는 x보다 더 큰 칸을 점프해야 합니다. 이때 처음은 몇칸을 뛰던 전혀 상관이 없습니다. 그러나 반드시 N번째 징검다리는 도달해야 합니다.

이때 최대한 징검다리를 많이 건널때 개수를 구하시오

 

해설 : 먼저 가장 많은 징검다리를 건너기 위해선 어떻게 해야될까요???우린 한번 가정을 해봅시다.

만약 n이 9이고 처음 4칸을 뛰었다고 해봅시다. 그러면 다음에 뛸때는 무조건 4칸보다 더 많이 뛰어야 하고 반드시 9번째 징검다리에 도달을 해야하니 5칸을 뛰면 되겠죠. 그러면 총 2개의 징검다리를 건너게 됩니다.

그러나 이는 최대값이 아니라는 것을 우린 알 수 있습니다.

처음에 1칸을 뛰고 그다음 3칸을 뛰고 그 다음 5칸을 뛰면 총 3개로 전보다 더 많은 징검다리를 건널 수 있게 되니까요

즉, 최소한의 간격으로 건널때가 최대한 많은 징검다리를 건널 수 있게 되는 겁니다.

(1+2+3+.....+k-1+k) 이렇게 말이죠.

이것은 1~k까지의 합이 됩니다. 근데 의문점이 들 수 있으신게 '반드시 N번째 징검다리에는 도달을 해야한다'라고 적혀있는데 저 공식의 결과값이 N이 되지 않는 경우도 존재할 수 있다는 겁니다.

 

그러나 이는 전혀 상관이 없습니다. 이유는 공식을 사용해서 나온 값이 N이 아닐지라도 우린 맨 마지막에 점프한 값을 교체해서 N으로 맞추어줄 수 있다는 거죠.

예)N이 9일때 1+2+3<9 입니다. (4까지 더해버리면 9를 벗어나기 때문에 안되겠죠)

그럼 우린 3이라는 수를 그냥 6으로 교체를 해버리는 것 입니다. 그럼 1+2+6 = 9 가 되서 문제를 해결할 수 있는 것이죠.

 

이 k값을 우린 이분탐색을 사용해서 구하면 됩니다. 만약 N보다 크다면 k값을 줄여주면 되고 N보다 작다면 k값을 늘려주면 되겠죠.

 

이때 주의할 점은 k*(k+1) 이라는 값이 long long형을 넘어갈 수 있습니다. 그래서 unsigned long long 형을 사용하시면 됩니다.......라고 생각하면 큰 '착각'입니다. 이유는 결국 경계값(10^16)이 입력으로 주어진다면 unsigned long long 형의 범위도 벗어나서 오버플로가 발생합니다. 다만, unsigned long long형의 오버플로는 UB가 아니라는 점때문에 '확률'상 통과가 될 수도 있는 것 입니다.

 

이를 배제하고 다시 문제를 보면 아무리 k값이 크다고 할지라도 시그마(k) 가 10^16을 넘어가는 범위는 10^9 보다 작다는 것을 단순계산으로도 구할 수 있습니다. 답의 상한을 생각하고 범위를 지정해 주면 되겠죠.

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using ll = long long;

void solve();
bool f(ll n, ll k);

int main()
{
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}
void solve()
{
	ll n;
	cin >> n;

	ll ans = 0;
	ll l = 1, r = (ll)1e9;
	while (l <= r)
	{
		ll mid = (l + r) / 2;
		if (!f(n, mid))
			r = mid - 1;
		else {
			ans = mid;
			l = mid + 1;
		}
	}
	cout << ans << "\n";
}
bool f(ll n, ll k)
{
	ll alpa = k * (k + 1) / 2;
	if (alpa <= n)
		return true;
	else
		return false;
}