[백준,c++] 11561번 - 징검다리

문제

11561번: 징검다리

 

코드

#include <iostream>
#include <cmath>
#define ll unsigned long long int
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T; cin>>T;
    while(T--){
        ll n; cin>>n;
        ll start = 1, end = 1e16;
        ll ans = 0;
        while(start <= end){
            ll mid = (start + end) / 2;
            if(mid * (mid+1) <= 2*n){
                ans = max(ans, mid);
                start = mid+1;
            }
            else end = mid - 1;
        }
        cout<<ans<<'\n';
    }
}

 

풀이

이분 탐색 문제입니다.

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

다음 조건을 이용해서 N번까지의 징검다리가 있을 때 밟을 수 있는 징검다리의 최대 수는 잘 생각해보면 아래와 같습니다.

1 + 2 + 3 + 4 + 5  + ..... (N-2) + (N-1) + N

위 식은 등차수열로써 (N * (N+1)) / 2로 표현할 수 있습니다.

따라서 1 ~ 10^16 까지의 수중 하나를 이분 탐색으로 선택했을 때 해당 값의 등차수열의 합이 N보다 작을 때의 최댓값을 찾아서 출력하면 됩니다.