[프로그래머스 알고리즘 스터디] 3주차 - 사탕 담기

YUZAMIN
YUZAMIN
Hello, World! I'm YUZAMIN, a diligently endeavoring frontend developer 🐤💦
[프로그래머스 알고리즘 스터디] 3주차 - 사탕 담기

Summary

문제 설명 📑

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

제한사항 🚫

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

문제 풀이 👩🏻‍💻

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 사탕 담기
from itertools import combinations


def solution(m, weights):
    answer = 0

    # 1부터 weights의 길이만큼 순회
    for i in range(1, len(weights) + 1):
        # weights 배열 내 요소를 i개만큼 선택
        weights_combinations = list(combinations(weights, i))

        # weights_combinations를 순회
        for combination in weights_combinations:

            # combination의 합이 m일 경우 answer에 1을 더함
            if sum(combination) == m:
                answer += 1

    return answer

문제 출처