[백준 11561번] 징검다리 (C++)

문제링크 : https://www.acmicpc.net/problem/11561

11561번: 징검다리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T;
    cin >> T;
    
    while(T--)
    {
        ll N, result = 0;
        cin >> N;

        ll l = 1, r = sqrt(N) * 2;
        while(l<=r)
        {
            ll mid = (l+r)/2;
            if (mid * (mid+1) <=2*N) // m(m+1)/2 <= N
            {
                result = max(result, mid);
                l = mid + 1;
            }
            else r = mid - 1;
        }
        cout << result << "\n";
    }


    return 0;
}

이분탐색을 이용한 문제이다.

규칙을 보면, 1 + 2 + 3 + 4 + ....... (N-1) + N번으로 이는 등차수열이다.

따라서 m(m+1)/2로 표현이 가능하며 여기서 m이 mid 값이다.

해당 등차수열의 값이 N보다 작을 때의 최대값을 구하면 된다.