2293번 파이썬

이 문제는 저번에 풀었던 동전2 문제랑 비슷한 유형인데 이번에는 동전의 개수가 아닌 경우의 수를 구하는 문제이다.

또한, 경우의 수 중에 중복되는게 있으면 안된다는 조건 때문에 생각을 좀 오래했다.

이 문제는 ary 반복을 돌린다음 1~k까지 반복을 돌렸는데 그 이유는 두 위치를 바꿔서 돌리게 되면 중복되는 경우의 수가 포함되기 때문이다.

그래서 아래 코드처럼 ary 다음에 1~k까지 반복을 했다.

이렇게 하면 예제처럼 1,2,5일 경우 모든 p에 1로만 이루어져있는 경우가 들어가고 그 다음에 2가 포함되는 경우가 들어가게 된다. 그 다음도 마찬가지로 5가 포함되는 경우가 들어가게 된다. 이렇게 되면 경우의 수는 반복되지 않게 된다!

ex)

1 / 1,1  / 1,1,1 / 1,1,1,1  / 1,1,1,1,1

x  /  2  / 1,2  /  1,1,2 2,2 / ...

이런 식으로 반복된다!  

**p[0]를 1로 초기화한 이유는 ary에 있는 동전 하나로만 만들때 1이 되기 때문이다..!

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ary = [int(input()) for _ in range(n)]
p = [0 for _ in range(k+1)]
p[0]=1
for i in ary:
  for num in range(1,k+1):
    if num-i >= 0:
      p[num]+=p[num-i]
print(p[k])