Python에서 인도 교단을 사용하여 n R.s를 얻을 수 있는 방법의 수를 찾는 프로그램

<시간/>

액면가가 제한된 동전(₩1, ₩2, ₩5 및 ₩10)이 있다고 가정합니다. 우리는 당신이 그것들을 총 ₩n으로 합할 수 있는 방법의 수를 찾아야만 합니다. 크기가 4인 배열 개수가 있으며 여기서 count[0]은 1루피의 코인을, count[1]은 2루피의 코인을 나타내는 식입니다.

따라서 입력이 n =25 count =[7,3,2,2]와 같으면 출력은 9가 됩니다.

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

데놈 :=[1,2,5,10]
A :=크기(n + 1)이고 0으로 채워지는 배열
B :=A의 새 목록
0에서 (count[0] 및 n의 최소값) 범위에 있는 i에 대해
- A[i] :=1
1~3 범위의 i에 대해 다음을 수행합니다.
- 0 범위의 j가 [i]를 계산하려면 다음을 수행합니다.
  - 0 ~ n + 1 - j *denom[i] 범위의 k에 대해, do
    - B[k + j * denom[i]] :=B[k + j * denom[i]] + A[k]
- 0에서 n 사이의 j에 대해 다음을 수행합니다.
  - A[j] :=B[j]
  - B[j] :=0
반환 A[n]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

denom = [1,2,5,10]
def solve(n, count):
   A = [0] * (n + 1)
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 25
count = [7,3,2,2]
print(solve(n, count))

입력

25, [7,3,2,2]