Python에서 N개의 오렌지를 먹을 수 있는 최소 일수를 찾는 프로그램

<시간/>

숫자 n이 있다고 가정합니다. 따라서 부엌에 n개의 오렌지가 있다고 가정하고 우리는 다음 규칙을 유지하면서 매일 이러한 오렌지 중 일부를 먹습니다. 1. 단일 오렌지를 먹습니다. 2. n이 짝수이면 n/2개의 오렌지를 먹습니다. 3. n이 3으로 나누어 떨어지면 2*(n/3)개의 오렌지를 먹을 수 있습니다. 우리는 매일 하나의 옵션만 선택할 수 있습니다. n개의 오렌지를 먹기 위한 최소 일수를 찾아야 합니다.

따라서 입력이 n =10과 같으면 출력은 4가 됩니다.

첫째 날에는 오렌지 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 =0을 먹습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

fun() 함수를 정의합니다. n
소요됩니다.
n이 메모에 있으면
- 회신 메모[n]
n<=2이면
- 반환 n
메모[n]:=1 + (n mod 2+ fun(n/2의 몫)) 및 (n mod 3 + fun(n/3의 몫))의 최소값
회신 메모[n]
기본 방법에서 다음을 수행하십시오.
메모:=새 지도
리턴 재미(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 = 12
print(solve(n))

입력

7, [5,1,4,3]