(C++) - 백준(BOJ) 11561번 : 징검다리 답

www.acmicpc.net/problem/11561

11561번: 징검다리

이분탐색문제였습니다.

 

풀이방법

 1. 최대의 징검다리를 밟을 경우는 무조건 이전거리보다 1만큼만 더 뛰는 것입니다. 따라서 매번 뛰는 횟수들을 계산했을 때 1의 등차를 가진 수열의 형태로 뛸 거리가 정해집니다. 징검다리 개수를 m개라고 했을 때 m(m+1)/2 <= n이라는 공식을 만들 수 있습니다. 이 답을 찾기 위해 이분탐색을 해줍니다.

 2. 따라서 1씩 증가하는 등차수열의 합이 n보다 작거나 같으면 l = mid+1로 만든 후, 답을 갱신해줍니다. else의 경우에는 r = mid - 1로 범위를 갱신해줍니다.

 3. 10^16은 1경입니다. m*m형태로 비교하므로 m이 sqrt(long long의 최대범위)를 초과한다면 if문에서 비교할 때 overflow가 날 수 있습니다. 이를 해결하기 위해 unsigned long long으로 자료형을 수정한 후 ac를 받았습니다.

 

Code

#include <iostream>
#include <vector>
#include <cmath>
#define ull unsigned long long
using namespace std;
ull binarySearch(ull n){
    ull l = 1;
    ull r = sqrt(n) * 2;
    ull mid = 0;
    ull ans = 0;
    while(l<=r){
        mid = (l+r)/2;
        if(mid*(mid+1) <= 2 * n) ans = max(ans,mid), l = mid+1;
        else r = mid-1;
    }
    return ans;
}
int main(){
    ull t,n;
    cin >> t;
    while(t--){
        cin >> n;
        cout << binarySearch(n) << '\n';
    }
}