코인 변경을 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 우리는 N개의 코인을 받았고 S의 각 값이 무한대로 공급되도록 해당 코인을 변경하려고 합니다. 순서에 관계없이 변경을 수행할 수 있는 방법의 수를 표시해야 합니다.

시간 복잡성을 줄이기 위해 문제 설명을 해결하기 위해 동적 프로그래밍 개념을 사용할 것입니다.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

# dynamic approach
def count(S, m, n):
   # base case
   table = [[0 for x in range(m)] for x in range(n+1)]
   # for n=0
   for i in range(m):
      table[0][i] = 1
   # rest values are filled in bottom up manner
   for i in range(1, n+1):
      for j in range(m):
         # solutions including S[j]
         x = table[i - S[j]][j] if i-S[j] >= 0 else 0
         # solutions excluding S[j]
         y = table[i][j-1] if j >= 1 else 0
         # total
         table[i][j] = x + y
   return table[n][m-1]
# main
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print(“Number of coins:”,end=””)
print(count(arr, m, n))

출력

Number of coins:6

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서 우리는 동전 교환을 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.