C++로 ax² + bx + c ≥ k를 만족하는 최소 양의 정수 x 구하기

문제 개요

네 개의 정수 a, b, c, k가 주어졌을 때, 다음 부등식을 만족하는 최소의 양의 정수 x를 찾는 문제입니다.

ax² + bx + c ≥ k

예를 들어 a = 3, b = 4, c = 5, k = 6이라면, x = 1일 때 3×1² + 4×1 + 5 = 12 ≥ 6이 성립하므로 정답은 1이 됩니다.

접근 방법: 이분 탐색(Bisection)

f(x) = ax² + bx + c는 a > 0일 때 x에 대해 단조 증가하는 함수입니다. 이 성질을 활용하면 이분 탐색을 통해 답을 매우 효율적으로 찾을 수 있습니다.

x는 최소 양의 정수여야 하므로 탐색 범위의 하한은 0으로 설정합니다. 상한은 k − c로 잡을 수 있는데, x = k − c이면 ax² + bx ≥ k − c가 항상 성립하기 때문입니다.

알고리즘 동작 과정

1. k ≤ c라면 x = 0일 때 이미 조건을 만족하므로 0을 반환합니다.
2. left = 0, right = k − c로 설정하고 이분 탐색을 시작합니다.
3. mid 값에 대해 val = a·mid² + b·mid를 계산합니다.
4. val > k − c이면 mid를 후보로 저장하고, 더 작은 값을 찾기 위해 right = mid − 1로 갱신합니다.
5. val < k − c이면 left = mid + 1로 갱신합니다.
6. val == k − c이면 mid가 정확한 답이므로 즉시 반환합니다.

C++ 구현 코드

#include<iostream>
using namespace std;
int getMinX(int a, int b, int c, int k) {
    int x = INT8_MAX;
    if (k <= c)
        return 0;
    int right = k - c;
    int left = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        int val = (a * mid * mid) + (b * mid);
        if (val > (k - c)) {
            x = min(x, mid);
            right = mid - 1;
        }
        else if (val < (k - c))
            left = mid + 1;
        else
            return mid;
    }
    return x;
}
int main() {
    int a = 3, b = 2, c = 4, k = 15;
    cout << "Minimum value of x is: " << getMinX(a, b, c, k);
}

실행 결과

Minimum value of x is: 2

a = 3, b = 2, c = 4, k = 15인 경우를 살펴보겠습니다. x = 1일 때는 3 + 2 + 4 = 9 < 15로 조건을 만족하지 못하지만, x = 2일 때는 3×4 + 2×2 + 4 = 20 ≥ 15가 되므로 최솟값은 2입니다.

시간 복잡도

이분 탐색을 사용하면 O(log(k − c)) 시간 안에 답을 구할 수 있습니다. 반면 x를 1부터 하나씩 증가시키며 확인하는 선형 탐색은 최대 O(√k)까지 걸릴 수 있으므로, 이분 탐색이 훨씬 효율적인 선택입니다.

참고: 실제 프로덕션 코드에서는 초기값으로 INT8_MAX(최댓값 127)보다 climits 헤더의 INT_MAX를 사용하는 것이 더 안전합니다.