[코딩테스트/Python] 프로그래머스 코딩테스트 - 사탕 담기

문제 설명
m 그램(gram)을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수를 구하려 합니다. 단, 같은 사탕은 또 넣을 수 없습니다.

가방이 감당할 수 있는 무게 m, 사탕별 무게가 담긴 배열 weights가 매개변수로 주어질 때, 가방을 정확히 m 그램으로 채우는 경우의 수를 return 하는 solution 함수를 작성해주세요.

제한 조건
m은 1,000 이상 100,000 이하인 자연수입니다.
모든 사탕의 무게는 10 이상 100,000 이하인 자연수입니다.
weights의 길이는 3 이상 15 이하입니다.

입출력 예

 

문제 풀이

# itertools의 combinations 이용 (파이썬 기본 라이브러리)
from itertools import combinations

def solution(m, weights):
    answer = 0
    
    for i in range(1, len(weights)):
        for c in list(combinations(weights, i)): # i(갯수) 별 모든 조합을 생성
            if sum(c) == m: # 조합의 합 중 m(감당 무게)와 같은 값이 있을 경우 count 1 추가
                answer += 1
    return answer

경우의 수 문제이기 때문에 파이썬 표준 라이브러리인 itertools의 combinations(조합)을 이용했다. 해당 리스트의 크기 별 조합을 모두 구해 기준 무게인 m과 조합의 합이 같은 경우에만 카운트 하도록 했다.