Python으로 비용·수량 범위 내에서 주어진 비율을 만족하는 조합 찾기

비용이 lowCost부터 upCost 사이의 범위에 있고, 수량이 lowQuant부터 upQuant 사이의 범위에 있다고 가정해 봅시다. 이때 비율 r = 비용 ÷ 수량을 만족하는 조합이 실제로 존재하는지 확인하는 것이 문제입니다.

예를 들어, 입력이 lowCost = 2, upCost = 10, lowQuant = 3, upQuant = 9, r = 3이라면 결과는 True입니다. 비용 = r × 수량 = 3 × 3 = 9로 계산했을 때, 비용 9는 범위 [2, 10] 안에 있고 수량 3 역시 범위 [3, 9] 안에 있기 때문입니다.

해결 접근 방법

가장 직관적인 방법은 가능한 모든 수량을 하나씩 검사하는 것입니다. 절차는 다음과 같습니다.

• 수량 범위(l_quant부터 u_quant까지)의 각 값 i를 순회합니다.
• 각 수량에 대해 비용 res = i × ratio를 계산합니다.
• 계산된 비용이 l_cost ≤ res ≤ u_cost 조건을 만족하는지 확인합니다.
• 만족하는 값이 하나라도 있으면 즉시 True를 반환하고, 끝까지 없으면 False를 반환합니다.

구현 예제

다음 코드를 통해 더 쉽게 이해할 수 있습니다.

def can_we_find_r(l_cost, u_cost, l_quant, u_quant, ratio) :
    for i in range(l_quant, u_quant + 1) :
        res = i * ratio
        if (l_cost <= res and res <= u_cost) :
            return True
    return False

l_cost = 2
u_cost = 10
l_quant = 3
u_quant = 9
ratio = 3

print(can_we_find_r(l_cost, u_cost, l_quant, u_quant, ratio))

입력

2, 10, 3, 9, 3

출력

True

개선된 방법: O(1) 수학적 풀이

범위가 매우 넓다면 위의 반복문 방식은 비효율적일 수 있습니다. 비율이 양의 정수라면 반복문 없이 수학적으로 바로 판별할 수 있습니다. 비율을 만족하는 수량은 l_cost / ratio 이상이면서 u_cost / ratio 이하여야 하므로, 이 구간이 주어진 수량 범위와 겹치는지만 확인하면 됩니다.

import math

def can_we_find_r_fast(l_cost, u_cost, l_quant, u_quant, ratio) :
    min_q = max(l_quant, math.ceil(l_cost / ratio))
    max_q = min(u_quant, u_cost // ratio)
    return min_q <= max_q

print(can_we_find_r_fast(2, 10, 3, 9, 3))  # True

이 방식은 데이터 크기와 무관하게 상수 시간에 답을 구할 수 있어, 범위가 클 때 특히 유용합니다.