C++로 지정된 범위 내에서 팩 크기 판별하기

두 개의 숫자 l과 r이 주어졌다고 가정해 보겠습니다. 어느 가게에서는 할인된 가격으로 'a'개의 식품이 들어 있는 용기를 판매하고 있으며, 어떤 고객이 x개의 식품을 구매하려고 합니다. 이 고객은 다음과 같은 탐욕적인(greedy) 전략을 따릅니다.

먼저 할인 가격으로 floor(x/a)팩을 구매합니다.
이후 남은 (x mod a)개는 하나씩 낱개로 구매하려고 합니다.

그러나 고객은 탐욕적이기 때문에, 남은 (x mod a)개를 낱개로 사려다가 (x mod a) ≥ a/2 조건이 성립하면 오히려 a개가 든 팩 하나를 통째로 구매해 버립니다.

고객은 l부터 r까지(양 끝값 포함) 범위 안에서 임의의 개수를 구매할 수 있습니다. 이때 우리가 확인해야 할 것은, 모든 고객이 처음 의도한 양보다 더 많은 식품을 구매하게 만드는 팩 크기 a가 존재하는지 여부입니다.

예를 들어 입력이 l = 3, r = 4라면 출력은 True가 됩니다. a = 5로 설정하면, 3개 또는 4개를 구매하려던 고객 모두 결국 한 팩(5개)을 통째로 사게 되기 때문입니다.

문제 해결 접근 방법

이 문제는 다음과 같은 간단한 조건 검사만으로 해결할 수 있습니다.

r / 2 >= l 이면:
    false 반환
그렇지 않으면:
    true 반환

동작 원리

핵심 아이디어는 r이 l의 두 배보다 작은 경우, 즉 r / 2 < l일 때 l보다 크거나 같으면서 2l 이하인 팩 크기 a를 선택할 수 있다는 점입니다. 이렇게 하면 범위 내 모든 구매량 x는 팩 크기 a보다 작으면서 a의 절반 이상이 되므로, 고객은 항상 팩 하나를 통째로 구매하게 됩니다. 반대로 r / 2 >= l이라면 이러한 조건을 만족하는 팩 크기를 찾을 수 없습니다.

예시 코드

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(int l, int r){
    if (r / 2 >= l)
        return false;
    else
        return true;
}
int main(){
    int l = 3;
    int r = 4;
    cout << solve(l, r) << endl;
}

입력

3,4