C++로 주어진 비용·수량 범위에서 원하는 비율을 얻을 수 있는지 확인하는 방법

문제 개요

비용의 범위(lowCost ~ upCost)와 수량의 범위(lowQuant ~ upQuant)가 주어졌을 때, 비율 r = cost / quantity를 만족하는 비용과 수량의 조합이 존재하는지 판별하는 문제입니다. 이때 비용과 수량은 각각 다음 조건을 반드시 만족해야 합니다.

• lowCost <= cost <= upCost
• lowQuant <= quantity <= upQuant

입력 예시 1

lowCost = 2, upCost = 10,
lowQuant = 3, upQuant = 9
r = 3

출력

Yes

설명

여기서 cost = r × quantity = 3 × 3 = 9이며, 이 값은 비용 범위 [2, 10]과 수량 범위 [3, 9] 모두에 속하므로 답은 Yes입니다.

입력 예시 2

lowCost = 15, upCost = 31,
lowQuant = 6, upQuant = 13
r = 8

출력

No

설명

cost = r × quantity = 8 × 6 = 48로 계산되지만, 이 값은 비용 범위 [15, 31]을 벗어나기 때문에 수량이 유효 범위 내에 있더라도 답은 No가 됩니다.

풀이 접근법

문제의 정의에 따르면 비율은 다음 관계식으로 표현할 수 있습니다.

cost = quantity × r

여기서 r은 비용과 수량 사이의 비율을 의미합니다. 이 식을 활용하면 해결 로직을 간단하게 도출할 수 있습니다. 수량 범위 내의 모든 값에 대해 r을 곱한 결과(계산된 비용)가 lowCost 이상이면서 upCost 이하인지 하나씩 검사합니다. 조건을 만족하는 값이 하나라도 존재하면 Yes를, 그렇지 않으면 No를 출력하면 됩니다.

C++ 구현 예제

// C++ 프로그램: 비율 r을 얻을 수 있는지 확인
#include <bits/stdc++.h>
using namespace std;

// 주어진 비용과 수량 범위에서
// 비율 r을 만들 수 있으면 true 반환
bool isRatioPossible(int lowCost, int upCost,
                     int lowQuant, int upQuant,
                     int r){
    // 수량 범위의 모든 값을 순회
    for (int i = lowQuant; i <= upQuant; i++){
        // 현재 수량 i에 대응하는 비용 계산
        int ans = i * r;
        // 계산된 비용이 허용 범위 안에 있는지 확인
        if (lowCost <= ans && ans <= upCost)
            return true;
    }
    return false;
}

// 드라이버 코드
int main(){
    int lowCost = 2, upCost = 10,
        lowQuant = 3, upQuant = 9,
        r = 3;
    if (isRatioPossible(lowCost, upCost,
                        lowQuant, upQuant, r))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

출력

Yes

복잡도 분석

이 알고리즘의 시간 복잡도는 O(upQuant − lowQuant + 1)로, 수량 범위의 크기에 비례하여 선형적으로 증가합니다. 추가적인 저장 공간 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.