C++ 이진 탐색으로 단조 증가 수열에서 특정 값의 위치 찾기

개념 이해하기

정수 l과 아래와 같은 단조 증가(mono­tonic increasing) 수열이 주어졌다고 가정해 봅시다.

f(m) = am + bm·[log₂(m)] + cm³

여기서 계수는 각각 a = 1, 2, 3, …, b = 1, 2, 3, …, c = 0, 1, 2, 3, … 입니다. 이때 [log₂(m)]은 밑이 2인 로그를 취한 뒤 소수점 이하를 버리고 내림한 값을 의미합니다. 따라서 그 결과는 다음과 같습니다.

• m = 1일 때 → 값은 0
• m = 2~3일 때 → 값은 1
• m = 4~7일 때 → 값은 2
• m = 8~15일 때 → 값은 3

우리의 과제는 f(m) = l을 만족하는 m의 값을 찾는 것입니다. 만약 l이 이 수열에 속하지 않는다면 0을 출력해야 합니다.

참고로 모든 값은 64비트 정수로 표현 가능하며, 세 정수 a, b, c는 각각 100을 초과하지 않습니다.

입력 예시

a = 2, b = 1, c = 1, l = 12168587437017

출력 예시

23001
f(23001) = 12168587437017

입력 예시 2

a = 7, b = 3, c = 0, l = 119753085330

출력 예시 2

1234567890

해결 방법

1. 단순 접근법 (Naive Approach)

주어진 a, b, c 값에 대해 모든 m에 대한 f(m) 값을 하나씩 계산하고, 그 값이 l과 일치하는지 비교하는 방식입니다. 구현은 간단하지만 탐색 범위가 클 경우 시간이 오래 걸린다는 단점이 있습니다.

2. 효율적인 접근법 — 이진 탐색 (Binary Search)

수열이 단조 증가하므로 이진 탐색을 활용하면 훨씬 빠르게 답을 찾을 수 있습니다. m의 최솟값(min)과 최댓값(max)을 정한 뒤, 중간값 m = (min + max) / 2를 기준으로 다음과 같이 탐색 범위를 좁혀 나갑니다.

• f(m) < l이면 → m을 증가시킵니다 (탐색 범위를 오른쪽 절반으로).
• f(m) > l이면 → m을 감소시킵니다 (탐색 범위를 왼쪽 절반으로).
• f(m) = l이면 → 해당 m이 바로 원하는 답입니다.

이 과정을 답을 찾거나 수열에 존재하지 않음이 확인될 때까지 반복합니다.

C++ 구현 예제

// C++ 구현 예제
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;

// 주어진 a, b, c, m에 대해 f(m) 값을 반환하는 함수
long long func(long long a1, long long b1, long long c1, long long m){
    long long res1 = a1 * m;
    long long logVlaue1 = floor(log2(m));
    res1 += b1 * m * logVlaue1;
    res1 += c1 * (m * m * m);
    return res1;
}

long long getPositionInSeries1(long long a1, long long b1,
    long long c1, long long l){
    long long start1 = 1, end1 = SMALL_N;
    // c가 0이면 m은 10^15 크기까지 가능
    // c가 0이 아니면 m^3 값이 10^18 크기를 가져야 하므로
    // m의 최댓값은 10^6 수준
    if (c1 == 0) {
        end1 = LARGE_N;
    }
    long long ans1 = 0;
    // 효율적인 탐색을 위해 이진 탐색 적용
    while (start1 <= end1) {
        long long mid1 = (start1 + end1) / 2;
        long long val1 = func(a1, b1, c1, mid1);
        if (val1 == l) {
            ans1 = mid1;
            break;
        }
        else if (val1 > l) {
            end1 = mid1 - 1;
        }
        else {
            start1 = mid1 + 1;
        }
    }
    return ans1;
}

// 드라이버 코드
int main(){
    long long a1 = 2, b1 = 1, c1 = 1;
    long long l = 12168587437017;
    cout << getPositionInSeries1(a1, b1, c1, l)<<endl;

    long long a2 = 7, b2 = 3, c2 = 0;
    long long l1 = 119753085330;
    cout << getPositionInSeries1(a2, b2, c2, l1)<<endl;

    long long a3 = 6, b3 = 2, c3 = 1;
    long long l2 = 11975309533;
    cout << getPositionInSeries1(a3, b3, c3, l2)<<endl;

    return 0;
}

실행 결과

23001
1234567890
0

코드 설명 및 핵심 포인트

위 코드에서 주목할 부분은 탐색 상한(end)의 설정 방식입니다. c가 0이 아니면 세제곱 항(cm³)이 지배적이 되어 m³ 값이 64비트 정수 한계인 약 10¹⁸에 도달해야 하므로, m의 최댓값은 대략 10⁶(SMALL_N)이면 충분합니다. 반면 c가 0이면 f(m)은 선형 항과 로그 항만으로 구성되므로 m이 10¹⁵(LARGE_N)까지 커질 수 있어 상한을 넉넉하게 잡아야 합니다.

세 번째 입력(6, 2, 1, 11975309533)의 경우 해당 값이 수열에 존재하지 않으므로 결과로 0이 출력됩니다. 이처럼 이진 탐색을 활용하면 최대 O(log N)번의 비교만으로 답을 찾을 수 있어, 단순 순차 탐색보다 압도적으로 효율적입니다.