백준 - 11561

문제링크

문제 유형은 약간의 수학과 이진탐색에 관한 문제이다.

 

문제의 조건에 충족하면서 최대의 징검다리를 밟기 위해서는

1부터 1씩 늘어나는 수열 1, 2, 3 ... k 즉 각 항의 차이가 1인 등차수열을 합을 구하면 되는 문제이다.

 

등차수열의 합 S = (k * (k + 1)) / 2 를 구한뒤 이 수가 N(징검다리의 수)보다 작은지를 확인하면되는데

문제는 N이 10^16 이므로 k를 1부터 구한다면 시간초과가 날것이다.

 

여기서 이진탐색을 적용해 k를 구하면 문제가 해결된다.

---

소스코드는 다음과 같다.

#include <iostream>
using namespace std;

/*
마지막 징검다리는 꼭 밟아야한다.
첫번째는 아무곳이나 밟을수있고
두번째 점프부터는 이전 점프거리보다 1 이상 더 뛰어야한다.
가장 많이 밟고 가고싶어한다.

즉 n번째에 도달할 수 있는 최대 점프수를 찾는것
n은 10^16 이므로 최소범위를 찾지않으면 시간초과가 날것
*/

long long t;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> t;
    long long n;
    for (int i = 0; i < t; i++) {
        cin >> n;

        long long left = 0, right = 1e9, ans = 0;
        while (left <= right) {
            long long mid = (left + right) / 2;
            if (((mid * (mid + 1)) / 2) <= n) {
                ans = mid;
                left = mid + 1;   
            }
            else
                right = mid - 1;
        }
        cout << ans << '\n';
    }
}

---

햇갈렸던 부분

문제의 해결법 자체는 간단했지만 이진 탐색과정중 잘못된부분이 있어 시간을 꽤나 허비했다.

while (left <= right) {
    long long mid = (left + right) / 2;
    if (((mid * (mid + 1)) / 2) >= n) {
        ans = mid;
        right = mid - 1;
    }
    else
        left = mid + 1; 

이런식으로 처음에 ans를 갱신하는 부분을 right의 범위가 줄어들때로 만들어놔서 탐색 범위가 제대로 좁혀지지않았고, 특히 마지막 탐색범위가 좁아질때 올바른 답이 누락되는 부분이 있었다.

 

이런 실수덕분에 이진 탐색에서 최대, 최소값을 찾을때 어떻게 해야하는지 명확히 알 수 있었다.

• 최대값을 찾는 경우는 조건이 만족될때 오른쪽으로 범위를 확장하고 값을 갱신한다.
• 최소값을 찾는 경우는 조건이 만족될때 왼쪽으로 범위를 줄이고 값을 갱신해야한다.