동전 1

면접 대비

시간 제한0.5초메모리 제한4 MB

요약

n가지 동전 종류가 있을 때, 순서를 무시하고 무제한으로 사용해 합이 정확히 k가 되는 조합의 수를 구합니다.

문제

서로 다른 가치를 가진 동전이 n종류 있다. 각 동전은 원하는 만큼 사용할 수 있다. 이 동전들을 사용해 합계가 정확히 k원이 되는 조합의 수를 구하라.

사용한 동전의 종류별 개수가 같다면, 동전을 나열한 순서만 다른 경우는 같은 방법으로 센다.

첫째 줄에 동전 종류의 수 n과 목표 금액 k가 주어진다. (1 <= n <= 100, 1 <= k <= 10,000)

다음 n개의 줄에는 동전의 가치가 하나씩 주어진다. 각 가치는 100,000 이하의 자연수이다.

합계가 k원이 되는 경우의 수를 첫째 줄에 출력한다. 경우의 수는 2^31보다 작다.