[Programmers][python] 9. 문제풀이 실습 (4): 프로그래머스 사탕 담기

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

프로그래머스 - 사탕 담기

---

문제 설명

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

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

---

제한조건

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

---

입출력 예

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

---

입출력 예 설명

사탕을 하나씩 선택해 3000 그램으로 만드는 방법은 [500, 1000, 1500], [1000, 2000], [500, 2500] 으로 3가지입니다.

---

생각

1. m과 weights의 범위는 크지만 입력의 크기는 아니기 때문에 무시해도 될 것 같습니다.
   그리고 List weights의 최대 길이가 15로 아주 작습니다.
   경우의 수를 뽑는 알고리즘을 이용해도 될 것 같습니다.

2. 그래서 저는 from itertools import combinations 패키지를 활용하여 경우의 수 조합으로 문제를 풀 것입니다.

3. for 반복문을 weight의 길이 만큼 반복하면서, weights에서 뽑는 개수를 조절하며 모든 경우의 수를 com List에 저장합니다.

4. 모든 경우를 확인하며 뽑은 경우의 합이 m이 되는지 확인합니다.

---

Code (Python)

from itertools import combinations

def solution(m, weights):
    answer = 0
    for i in range(len(weights)):
        com = list(combinations(weights, i+1))
        for j in com:
            if m == sum(j):
                answer += 1
    return answer

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.