[99클럽/코딩테스트 챌린지/C++] 징검다리 문제에서 이분 탐색으로 최대 징검다리 수 찾기

오늘은 징검다리 문제에서 이분 탐색을 활용하여 최대 몇 개의 징검다리를 밟을 수 있는지 찾는 풀이 방법을 정리했습니다. 이 문제에서 중요한 부분은 조건을 수식으로 변환하고, 오버플로우를 방지하는 이분 탐색을 사용하는 것이었습니다.

문제링크 : 

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

문제 접근 과정

1. 규칙 분석
   • 승택이는 N번 징검다리를 반드시 밟아야 하며, 이전에 밟았던 징검다리보다 1 이상 더 먼 거리를 점프해야 합니다. 예를 들어, 점프 거리가 1, 2, 3, ..., K가 되며, 이 점프들의 총합이 N을 넘지 않아야 합니다.
   • 이 규칙을 통해 등차수열의 합 공식을 적용할 수 있습니다: 합 =  K * (K + 1) / 2 ​
2. K 값 찾기 - 이분 탐색을 활용한 최대값 찾기
   • 이분 탐색을 통해 조건을 만족하는 최대 K를 찾습니다.
   • 각 K에 대해 점프 거리의 합인 K * (K + 1) / 2가 N보다 작거나 같은지 확인합니다.
   • 이때, 중간 값 mid를 K로 설정하고, 조건을 만족하면 K를 더 크게, 만족하지 않으면 더 작게 조정합니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

#include <iostream>
using namespace std;

long long maxStone(long long n) {
    long long left = 1, right = 1000000000;
    long long result = 1;

    while (left <= right) {
        long long mid = (left + right) / 2;

        // 오버플로우 방지: mid * (mid + 1) / 2 <= n 대신 (2 * n) >= mid * (mid + 1) 형태로 비교
        if (mid <= (2 * n) / (mid + 1)) {
            result = mid;     // 가능한 최대 K 저장
            left = mid + 1;   // 더 큰 K를 시도
        } else {
            right = mid - 1;  // 더 작은 K를 시도
        }
    }

    return result;
}

int main() {
    int t;
    cin >> t;

    while (t-- > 0) {
        long long n;
        cin >> n;
        cout << maxStone(n) << endl;
    }

    return 0;
}

배운 점

이 문제를 통해 이분 탐색과 오버플로우 방지 방법을 배울 수 있었습니다.

1. 이분 탐색의 활용 : 문제에서 특정 조건을 만족하는 최대값을 찾을 때 이분 탐색이 매우 유용하다는 점을 다시 확인했습니다. 큰 입력을 효율적으로 탐색할 수 있어 시간이 제한된 문제에서도 안정적입니다.
2. 단순한 조건일수록 효율적인 수식화 : 문제 조건을 수식으로 단순화하는 과정이 문제 해결의 핵심이었습니다. 등차수열의 합 공식이 문제에 잘 적용되었고, 이를 통해 문제 조건을 명확히 정의할 수 있었습니다.

결론

이 문제를 통해 이분 탐색을 통한 최적의 값 찾기와 수식 변형을 통한 오버플로우 방지라는 두 가지 중요한 기법을 익혔습니다. 앞으로는 문제에서 조건을 더 단순한 수식으로 표현하고, 이분 탐색을 유연하게 활용할 수 있도록 노력해야겠다고 느꼈습니다.