사탕담기 (python)

itertools.product 사용 (중복순열), 입력값이 작으므로 완전탐색으로 풀어도 괜찮은 문제

👀 깃헙 소스

문제설명
m 그램(gram)을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수를 구하려 합니다. 단, 같은 사탕은 또 넣을 수 없습니다.
가방이 감당할 수 있는 무게 m, 사탕별 무게가 담긴 배열 weights가 매개변수로 주어질 때, 가방을 정확히 m 그램으로 채우는 경우의 수를 return 하는 solution 함수를 작성해주세요.
weights의 길이는 3 이상 15 이하입니다

입출력 예

m	weights				return
3000	[500, 1500, 2500, 1000, 2000]	3

솔루션
각 사탕을 담는 경우와 담지 않는경우를 만든 후 product를 이용하여
모든 경우를 구한 후 합이 m이되는 경우를 세서 return 한다.

# or_not
[(0, 500), (0, 1500), (0, 2500), (0, 1000), (0, 2000)]

# itertools.product(*or_not)
[(0, 0, 0, 0, 0), (0, 0, 0, 0, 2000), (0, 0, 0, 1000, 0), (0, 0, 0, 1000, 2000), (0, 0, 2500, 0, 0), (0, 0, 2500, 0, 2000), (0, 0, 2500, 1000, 0), (0, 0, 2500, 1000, 2000), (0, 1500, 0, 0, 0), (0, 1500, 0, 0, 2000), (0, 1500, 0, 1000, 0), (0, 1500, 0, 1000, 2000), (0, 1500, 2500, 0, 0), (0, 1500, 2500, 0, 2000), (0, 1500, 2500, 1000, 0), (0, 1500, 2500, 1000, 2000), (500, 0, 0, 0, 0), (500, 0, 0, 0, 2000), (500, 0, 0, 1000, 0), (500, 0, 0, 1000, 2000), (500, 0, 2500, 0, 0), (500, 0, 2500, 0, 2000), (500, 0, 2500, 1000, 0), (500, 0, 2500, 1000, 2000), (500, 1500, 0, 0, 0), (500, 1500, 0, 0, 2000), (500, 1500, 0, 1000, 0), (500, 1500, 0, 1000, 2000), (500, 1500, 2500, 0, 0), (500, 1500, 2500, 0, 2000), (500, 1500, 2500, 1000, 0), (500, 1500, 2500, 1000, 2000)]

코드

# 파이썬
import itertools
def solution(m, weights):
    or_not = zip([0]*len(weights), weights)
    cand = itertools.product(*or_not)
    return list(map(sum,cand)).count(m)

주의
product안의 parameter는 *로 spread해준 후 넣어 주어야 한다.