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

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

11561번: 징검다리

 [문제 요약] 

- 강에 놓인 징검다리를 밟고 건너갈 것이다.

- 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.

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

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

- 다음과 같은 규칙으로 징검다리를 건넌다.

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

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

 

[문제 조건]

- 첫째 줄에 테스트 케이스의 수 T가 주어진다.

- 각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ 10^16)

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 어렵지 않으나, 문제를 잘못 읽으면 하루죙일 고민하게된다.

 

필자는 처음에 밟고 가는 징검다리의 개수를 최소로 해서 건너가게 하는 문제로 생각했는데(그냥 문제 잘못읽은거임) 알고보니 최대로 밟고서 강을 건너는 문제다.

 

그래서 한번 생각해보면, 아마 2번 규칙이 가장 핵심이 되는 문장이다.

 

다음 점프거리는 이전 점프거리보다는 커야된다. 그렇다면 징검다리를 최대로 밟으면서 2번 규칙을 만족 시키려면

1,2,3,4,..... 이런식으로 뛰다가 마지막 점프가 N번째 징검다리에 오게 만들면된다.

 

예를 들면 징검다리가 (N=11)일 때 1씩 커지는 방식으로 징검다리를 건너면 1+2+3+4 하고 1개의 징검다리가 남게된다.

이때 마지막점프에 남은 징검다리 수만큼 더해주면 건널 수 있게 된다. (1+2+3+5(4+1))

 

이것을 일반화 시키면 등차수열의 합 공식을 이용해  (K * (K+1))/2 의 값이 N을 넘지 않는 k를 구해주면 정답이 된다는 것이다.

 

다만 문제에서 주어지는 범위가 10의 16이라서 int로는 해결이 안되고 unsigned long long을 이용하여 이분탐색으로 적당한 K값을 찾을 수 있다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define MAX 10000000000000000

using namespace std;

unsigned long long tmp;

unsigned long long binary(unsigned long long start, unsigned long long end)
{
	while (start < end)
	{
		if (end - start == 1) return start;
		unsigned long long mid = (start + end) / 2;
		if ((mid * (mid + 1)) / 2 <= tmp) start = mid;
		else end = mid;
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	unsigned long long T;
	cin >> T;
	while (T--)
	{
		cin >> tmp;
		cout << binary(1, MAX) << "\n";
	}
}

 

굳