문제

치킨너겟을 각각 6개, 9개, 20개 담은 소/중/대 세 가지 크기의 박스로 판매한다. 그렇다면 박스 단위로만 구매할 때, 조합할 수 없는 가장 큰 치킨너겟 개수는 몇 개일까? (세 박스 용량의 최대공약수는 1이다. 두 개씩 서로소일 필요는 없다.)

예를 들어 치킨너겟 1개만 사는 것은 불가능하다. 최소 6개짜리 박스를 사야 하기 때문이다. 반면 15개는 가능하다. 6개짜리 하나와 9개짜리 하나를 사면 된다.

아래에서는 조합 가능성에 대한 수학적 설명과, 답을 구하는 알고리즘을 다룬다.

존재성

각 박스 용량을 $x_i$로 표기하자. 일반성을 잃지 않고 $x_i$는 엄격히 증가하는 수열이라고 해도 좋다. 여기서는 $x_1=6$, $x_2=9$, $x_3=20$이다. 또한 $\gcd(x_i) = 1$이라고 가정한다.

존재성을 증명한다는 것은, 어떤 값 $N$을 찾아 $N$ 이상의 모든 자연수가 조합 가능함을 보이는 것이다. 따라서 조합할 수 없는 수는 1 이상 $N$ 이하에만 존재한다.

최대공약수가 1이므로 $\sum_i{c_i x_i} = 1$을 만족하는 정수 $c_i$를 찾을 수 있다. $c_i^+=\max(c_i, 0)$, $c_i^-=-\min(c_i, 0)$으로 정의하자. 전자는 양수 부분만, 후자는 음수 부분의 절댓값만 취한 것이다. 그러면 $c_i=c_i^+-c_i^-$이고, $c_i^+$와 $c_i^-$는 모두 0 또는 양수이다.

$N=x_1 \sum_i c_i^-x_i$라고 하자. 여기서 $x_1=\min(x_i)$이다. 먼저 $k \ge 0$인 모든 $N + kx_1$에 대해 조합이 가능하다. $\sum_i c_i x_i = 1$이므로, $x_1$ 박스를 $k$개 더 추가하면 $N + kx_1$을 만들 수 있다.

$0 \le j \lt x_1$인 $j$에 대해서,

$$\begin{aligned} N+j&=x_1 \sum_i c_i^-x_i+j\sum_i{c_i x_i} \\ &=(x_1 - j) \sum_i c_i^-x_i+j\sum_i c_i^+x_i \end{aligned}$$

각 항의 계수가 모두 0 이상이 된다. 이 변형은 $0 \le j < x_1$일 때만 성립한다. 앞서 $N + kx_1$ 형태의 수는 모두 표현 가능하므로, $N + kx_1 + j$도 같은 논증으로 표현할 수 있다.

결과적으로 $N$ 이상의 모든 자연수는 표현 가능하므로, 답은 $N$ 미만에서 찾을 수 있다.

풀이

사실 박스가 2종류일 때는 닫힌 형태(closed form)의 답이 있지만, 3종류 이상에서는 알려진 일반 공식이 없다. 이 점은 아래 영상에서 확인할 수 있다.

이 문제는 알고리즘으로 풀어 보자.

우선순위 큐 q가 있고, 처음에는 0만 들어 있다고 하자. 이미 큐에 넣었던 값은 다시 넣지 않는다.

큐에서 꺼낸 원소 $e$마다 $e + x_i$를 큐에 넣는다. 언제 반복을 멈출지가 핵심인데, 꺼낸 값이 연속된 자연수로 $x_1$개 이상 이어지면 더 이상 확인할 필요가 없다. 정답은 그 연속 구간의 시작값에서 1을 뺀 값이다.

의사 코드는 다음과 같다.

def find_min_nugget(num_list: list[int]) -> int:
    """
    :param num_list: 정렬된 자연수 리스트
    :return: 조합할 수 없는 가장 큰 자연수
    """

    # Queue Initialize
    queue = HeapQueue()
    queue.put(0)

    # 연속인지 확인 용
    start_num = 0
    consecutive_count = 0
    
    while True:
        current = queue.get()
        for num in num_list:
            queue.put(current + num)

        # 연속인지 확인 및 종료 여부 체크
        if current == start_num + consecutive_count:
            consecutive_count += 1
            if consecutive_count >= num_list[0]:
                return start_num - 1
        else:
            start_num = current
            consecutive_count = 1

def main():
    print(find_min_nugget([6, 9, 20]))  # 결과는 43

마무리

$x_i$가 작을 때는 큰 문제가 되지 않지만, 결국 답에 이르기까지의 수를 하나씩 확인해야 한다. 더 빠른 방법이 있는지는 아직 나에게는 열린 문제로 남아 있다.

이 글은 아래 영상에서 영감을 받아 작성했습니다.

why you can't order 43 nuggets. @MichaelPennMath →