문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
m 그램을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수 찾기
중복 불가
가방에 담을 수 있는 무게 : m
사탕별 무게가 담긴 배열 : weights
1,000 <= m <= 100,000
10 <= 사탕의 무게 <= 100,000 3 <= weights의 길이 <= 15
입출력 예시
| m | weights | return |
|---|---|---|
| 3000 | [500, 1500, 2500, 1000, 2000] | 3 |
접근
그냥 완전탐색 문제이다.
모든 경우의 수를 검사해주자.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(m, weights):
answer = search(m, weights, 0, 0)
return answer
def search(m, weights, now, start):
if now == m:
return 1
elif now > m:
return 0
if start >= len(weights):
return 0
return search(m, weights, now+weights[start], start+1) + search(m, weights, now, start+1)