99클럽 코테 스터디 2일차 TIL + 이진탐색(C++)

문제

[백준] 11561번: 징검다리

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

 

최초 시도 (실패)

접근 방법

최대한 많은 수의 징검다리를 건너려면 우선 첫번째 징검다리를 현재 시작점에서 가장 가까운 곳으로 잡아야 하고, 한 번 점프할 때마다 최소한의 거리를 움직여야 한다.

문제 조건 상 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 하므로,

결론적으로는 시작점에서 가장 가까운 1번부터 시작해 다음 징검다리는 이전에 점프한 거리보다 1씩만 더 증가한 거리를 움직이게 하여야 한다.

항상 1 → 3 → 6 → 10 → 15 → 21 … 의 징검다리를 밟아가는 것이다.

이러려면 우선 내가 징검다리를 몇 번 밟았는지 카운트하는 변수 count와,

한번 점프할 때마다(반복문을 돌 때마다) 이전에 점프한 거리에 1을 더한 값인 변수 adder,

그리고 현재 징검다리의 위치를 나타내는 변수 temp가 있어야 한다.

이런 식으로 각 N에 대해 temp의 값을 증가시켜나가다가 temp가 N보다 같거나 커지면 count를 출력하고,

그렇지 않으면 count를 1 증가시키는 것을 반복해 나가는 과정을 코드로 표현했다.

 

코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    for (int i = 0; i < T; i++) {
        long long count = 0;
        long long adder = 0;
        long long temp = 0;
        long long N;
        cin >> N;
        
        // N이 1이면 하나밖에 못 밟으니까 1 출력
        if (N == 1) {
            cout << 1 << '\\n';
            continue;
        }
        
        while (temp < N) {
            adder++;
            temp += adder;
            
            if (temp >= N) {
                cout << count<< '\\n';
                break;
            }
            
            count++;
        }
    }
    
    return 0;
}

하지만 실패.

예제 케이스는 모두 통과했으나 시간 초과가 발생했다.

 

---

 

두번째 시도 (성공)

코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        long long N;
        cin >> N;
        
        long long low = 1, high = sqrt(2 * N), answer = 0;
        
        // 이진 탐색
        while (low <= high) {
            long long mid = (low + high) / 2;
            long long sum = mid * (mid + 1) / 2; // 등차수열의 합
            
            if (sum <= N) {
                answer = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        cout << answer << endl;
    }
    
    return 0;
}

풀이

1. 각 단계마다 점프하는 거리는 1, 2, 3, …, i와 같이 1씩 증가한다. 이렇게 1씩 증가하는 수열의 합은 등차수열의 합으로 계산할 수 있다. 등차수열의 합 1 + 2 + 3 + …+ k는 k(k+1)/2와 같은 수식으로 표현된다.
2. 점프 k를 할 때 필요한 거리는 1, 2, 3, ..., k이고, 이를 통해 점프의 합, 즉 k(k+1)/2이 징검다리 N 이하가 되도록 최대로 점프할 수 있는 k 값을 찾으면 된다.
3. 따라서 점프 거리를 1씩 증가시키면서 1 + 2 + 3 + ... + k <= N 조건을 만족하는 최대의 k를 찾는 방식으로 문제를 해결할 수 있다.

 

🔎 이진 탐색에서 high가 sqrt(2 * N)인 이유

high는 k에 대한 근사치로, 점프 횟수의 상한을 의미한다.

등차수열의 합 k(k+1)/2 를 N에 맞추어 대략적으로 근사할 때,

k(k+1)/2 = N의 양변에 2를 곱하면 k(k+1) = 2N 이고, k^2 + k = 2N이므로 k는 대략 sqrt(2 * N)으로 추정할 수 있다.

이렇게 점프 횟수의 상한을 근사치로 설정하고 이진 탐색을 사용하면 훨씬 효율적으로 k 값을 찾아갈 수 있다.