파이썬으로 N개의 오렌지를 모두 먹는 최소 일수 구하기

문제 개요

숫자 n이 주어지고, 주방에는 n개의 오렌지가 있다고 가정해 봅시다. 우리는 매일 아래 세 가지 규칙 중 단 하나만 선택해 오렌지를 먹어야 합니다.

• 오렌지 1개를 먹는다.

• n이 짝수라면 n/2개의 오렌지를 한 번에 먹는다.

• n이 3으로 나누어 떨어지면 2×(n/3)개의 오렌지를 한 번에 먹는다.

목표는 이 규칙을 지키면서 n개의 오렌지를 모두 먹는 데 필요한 최소 일수를 구하는 것입니다.

입력 예시와 단계별 풀이

예를 들어 n = 10일 때 정답은 4입니다. 과정을 살펴보면 다음과 같습니다.

• 1일차: 오렌지 1개 섭취 → 10 − 1 = 9

• 2일차: 오렌지 6개 섭취 → 9 − 2×(9÷3) = 9 − 6 = 3

• 3일차: 오렌지 2개 섭취 → 3 − 2×(3÷3) = 3 − 2 = 1

• 4일차: 마지막 오렌지 1개 섭취 → 1 − 1 = 0

풀이 접근 방식

이 문제는 메모이제이션(memoization)을 적용한 재귀 함수로 효율적으로 해결할 수 있습니다. 같은 값을 반복해서 계산하지 않도록 결과를 캐싱하는 것이 핵심입니다. 알고리즘은 다음 순서로 진행됩니다.

1. 정수 n을 인자로 받는 fun() 함수를 정의합니다.

2. n이 메모 딕셔너리(memo)에 이미 저장되어 있으면 저장된 값을 즉시 반환합니다.

3. n ≤ 2라면 남은 오렌지를 하루에 하나씩 먹는 것이 최선이므로 n을 그대로 반환합니다.

4. 그 외의 경우에는 두 가지 전략을 비교합니다.

   • 절반으로 줄이기: 나머지(n mod 2)만큼 하루에 하나씩 먹어 n을 2의 배수로 맞춘 뒤, 절반 나누기를 하루 수행하고 n//2에 대해 재귀 호출합니다.

   • 3등분으로 줄이기: 나머지(n mod 3)만큼 하루에 하나씩 먹어 n을 3의 배수로 맞춘 뒤, 2×(n/3)개를 하루에 먹고 n//3에 대해 재귀 호출합니다.

5. 두 전략 중 더 적은 일수에 당일(1일)을 더한 값을 memo[n]에 저장하고 반환합니다.

6. 메인 부분에서는 빈 딕셔너리 memo를 생성한 뒤 fun(n)을 호출해 결과를 반환합니다.

구현 예제

아래 파이썬 코드로 위 알고리즘을 직접 확인할 수 있습니다.

def solve(n):
    def fun(n):
        if n in memo:
            return memo[n]
        if n <= 2:
            return n
        memo[n] = 1 + min(n % 2 + fun(n // 2), n % 3 + fun(n // 3))
        return memo[n]

    memo = {}
    return fun(n)

n = 10
print(solve(n))

입력

10

출력

4

성능 분석

재귀 호출이 진행될수록 n이 1/2배 또는 1/3배로 빠르게 감소하기 때문에 탐색해야 하는 상태의 수가 로그 스케일로 제한됩니다. 여기에 메모이제이션으로 중복 계산까지 제거되므로, n이 매우 큰 경우에도 빠른 시간 안에 답을 구할 수 있는 매우 효율적인 풀이입니다.