거스름돈 최소값 구하는 파이썬 그리디 알고리즘 + 재귀 입니다. 제시 조건은 이렇습니다

지불해야 할 거스름돈 액수를 m이라 하자.

• 금액 m>0인 경우

  1. m < c_0이면, 그러니까 가장 큰 동전보다 적은 액수이면 그 동전은 필요없다. coins대신에 coins[1:]을 가능한 동전으로 취급하고 진행하면 된다는 말이다. 이 과정을 액수 m 이하의 동전이 coins의 처음에 나타날 때까지 반복한다.

  2. 위의 1번 단계에서 처리가 되었으므로 항상 m >= c_0이 된다.

     • c_0 > 1인 경우 두 가지로 경우로 나누어 필요한 동전 개수를 생각할 수 있다.

       • c_0짜리 동전을 아예 사용하지 않고 나머지 종류의 동전으로만 액수 m을 지불 (그러니까 여기서 재귀적으로 coins[1:]로 지불하는 경우 최소 동전 개수를 찾으면 됨)
       • c_0짜리 동전 1개를 일단 사용하고 남은 금액(m-c_0)을 지불 (그러니까 여기서 재귀적으로 m-c_0를 지불하는 경우 최소 동전 개수를 찾으면 됨)

       위 두 값 개수를 중에서 더 적은 동전 개수를 취해 리턴하면 된다.

     • c_0 = 1인 경우 m을 리턴한다. (1짜리 동전만으로 금액 m을 지불하려면 m개 필요)

• 금액 m=0인 경우 0을 리턴한다.

def coin_count(coins, m):
    if m > 0:
        while len(coins) > 0 and m < coins[0]:
            coins = coins[1:]  # 지불 금액보다 더 큰 단위의 동전 제외 [ 남은 지불 금액보다 동전이 큰것을 걸러줌 ] 
        if coins[0] > 1: 

            minCoins01 = m
            # C[1:] 사용 계산
            for i in [a for a in coins[1:] if a <= m]:
                numCoins01 = 1 + coin_count(coins,m - i)
                if numCoins01 < minCoins01:
                   minCoins01 = numCoins01

            print(minCoins01)
            # C[0] 동전 1개 이상 사용하는 계산
            minCoins02 = m
            for i in [b for b in coins if b <= m]:
                numCoins02 = 1 + coin_count(coins,m - i)
                if numCoins02 < minCoins02:
                   minCoins02 = numCoins02

            return min(minCoins01, minCoins02)
        else: # coins[0] == 1
            return m

    else: # m == 0
        return 0

my_coins = [50,40,20,10,5,4,2,1]
print(run_coin_count(my_coins,80))

코드를 작성하고 있는 중인데 중간 조건 2에서 coins[0]을 이용하지 않는 방법과 coins[0]도 이용 하는 조건으로 인해 재귀를 2번 돌아야 하는데 coins[0]을 이용하지 않는 방법을 재귀로 돈다음에 coins[0]을 이용하는 방법을 계산하려면 앞에서 이미 재귀가 돌아 원래값 m 값이 손상되어 진행이 안되는 상황입니다. 이 구조가 가능한 구조인가요?? 다른 방법을 찾아보고싶습니다