문제

BOJ 11561번 징검다리

나의 요약

1~N까지의 징검다리 존재한다. 제자리뛰기로 바로 이동이 가능하다.
1. 첫 징검다리는 점프해서 아무거나 밟을 수 있다.
2. 두번째는 이전에 점프한 거리보다 1 이상 긴 거리를 가야한다.
3. N번 징검다리를 반드시 밟음으로써 건너기를 마무리한다.
이 조건을 지킬 때 최대로 밟는 징검다리의 수는?

접근방식

최대로 밟는 징검다리의 수니까, 거리 1, 거리 2, 거리 3 이런식으로 등차수열을 보이면서 건너야한다. 맨 마지막 징검다리는 무조건 N번을 밟아야하니, 등차수열로 진행하면서도 N을 지나가는 등차수열이 되면 안된다. N을 지나기 전까지의 등차수열을 진행하면서 마지막은 바로 N으로 뛰어버리는 것이 가장 최대로 점프하는 방법일 것이다.

결국 등차수열로 점프를 했을 때의 점프 수에 대해서 (점프 수 + 1) * 점프 수 / 2가 N 이하인 최대의 점프 수를 구하면 된다.

N의 범위가 10^16로 꽤 큰 수이므로, 이분탐색으로 진행하면 괜찮겠다고 생각했다.

풀이

#include <bits/stdc++.h>
using namespace std;

void solve()
{
	unsigned long long N;
	cin >> N;
	
	unsigned long long left = 1, right = N;
	while(left <= right)
	{
		unsigned long long mid = (left + right) / 2;
		unsigned long long lastStone = (mid + 1) * mid / 2;
		
		if(lastStone > N)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	
	cout << right << '\n';
}

int main() {
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
	
	int T;
	cin >> T;
	
	for(int t = 0; t < T; t++)
	{
		solve();
	}
}

구체적인 풀이는 solve 함수를 보면 된다. 1과 N 사이에서 이분탐색을 진행한다. mid만큼 점프를 진행했다고 가정했을 때, 등차수열 점프로 나오는 마지막 돌인 lastStone이 N보다 큰지 검사한다. N보다 크다면 점프를 너무 많이 한 것이므로, 범위를 아래쪽으로 좁힌다. N 이하라면 조건은 만족하는 것이니, 더 큰 수들을 조사하러 범위를 위쪽으로 좁힌다.

left와 right는 각각 mid + 1, mid - 1을 하게 되는데, 이는 mid 값을 확실하게 탐색에서 제외하기 위해서다. 그냥 mid로만 범위를 좁히면 left와 right가 계속 같아져 무한루프에 걸리는 경우가 발생할 수 있기 때문에 유의하자.

헤맨 지점

처음에는 변수들을 long long으로만 잡았다가, lastStone을 구하는 과정에서 long long의 범위를 초과한다는 것을 알게 되었다. 어차피 양수만 나오는 계산이다 보니 unsigned long long으로 바꾸었고, 잘 해결되었다.

이분탐색

문제를 풀다보니 내가 left가 답이 되어야하는지, right가 답이 되어야하는지 빠르게 머릿속으로 정리가 되지 않았다. 이분 탐색에서의 두 가지 탐색 유형인 Lower Bound와 Upper Bound에 대해 제대로 짚고 넘어가보자.

Upper Bound

Upper Bound는 찾고자 하는 값을 초과하는 첫번째 위치를 찾는 유형이다. 예를 들어 1 3 3 5 5 같은 배열이 있을 때, 3에 대한 Upper Bound는 5가 들어있는 3 인덱스이다.
결국 특정 값을 초과하는 첫번째 위치를 알려주는 것이니, 여기서 -1만 하면 특정 값의 마지막 위치라는 뜻도 된다. 위의 문제는 N을 초과하는 첫번째 점프 수에서 -1한 것이 답이었으니, Upper Bound 유형이다.

보통 Upper Bound 유형은 초과하는 첫번째 위치를 구하는데, left가 초과하기 전까지 계속 +1을 진행하므로, 이분탐색이 끝났을 때 left가 답인 경우가 많다. 이번의 경우에는 그것의 -1이니, right나 left-1가 답이 된다.

Lower Bound

Lower Bound는 찾고자 하는 값 이상인 첫번째 위치를 찾는 유형이다. 예를 들어 1 3 3 5 5의 배열에서 3에 대한 Lower Bound는 3이 들어있는 1 인덱스이다.