이번 문제는 다이나믹 프로그래밍으로 해결하는 문제였다. 반복되는 연산을 저장하여 연산 횟수를 줄이는 다이나믹 프로그래밍의 장점을 이용했다.

• n, k 를 입력받는다.
• 동전의 금액을 입력받는 coin 배열을 선언하고 입력받는다.
• 동전의 합의 경우 수를 저장하는 answer 배열을 선언한다. 이때 answer 배열의 인덱스는 동전의 합을 의미한다. answer배열의 크기는 k+1이 된다.
  -> ex) answer[4]는 동전의 합이 4가 되는 경우의 수를 저장하는 원소이다.
• answer[0]은 1로 저장한다. 이는 answer[가장 작은 동전 금액]을 구하기 위함이다.
• 이중 for문을 통하여 값을 구한다.
  -> 바깥 for문은 i가 coin배열을 돌게 한다.
  -> 안쪽 for문은 j가 coin배열의 해당 원소부터 k까지 돌게 한다.
  -> 안쪽 for문에서 조건문을 통해 answer배열을 업데이트한다. 이때 조건은 j-i가 0보다 크거나 같은 경우이고, 조건문 안에서 answer[j]에 answer[j-i]를 더해준다.
• answer[k]를 출력한다. 이는 k원이 되는 경우의 수가 된다.

Code

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))
answer = [0]*(k+1)
answer[0] = 1
for i in coin:
    for j in range(i, k+1):
        if j-i>=0:
            answer[j] += answer[j-i]
print(answer[k])