
문제 설명
해골섬 주변에서 물고기를 잡던 캣은 거친 비바람을 만났습니다.
비바람이 너무 세서 집에 갈 수가 없다냥….
캣은 해골섬 해변에 배를 정박하고 하룻밤을 묵을 장소를 찾기 위해 해골섬 이곳저곳을 탐험하기 시작합니다. 해골섬에는 특이하게 여러 조각상이 널브러져 있었습니다. 그때 어디선가 스산한 목소리가 들려왔습니다.
누구냐, 산 자가 도달할 수 없는 곳에 도달한 자는…? 흥미롭구나, 꿈으로부터 도달하다니.
안갯속에서 망토를 입은 해골 한 마리가 둥둥 떠 다가왔습니다. 캣은 전설 하나가 기억났습니다. 오래전에, 신에게 저주받은 리치가 해골섬에 갇혀있으며 자신의 영역을 침범하는 고양이를 산 채로 돌로 만들어버린다는 전설이었습니다.
산 자가 들어올 수 없는 이곳에 들어온 욕심쟁이에게 욕심쟁이 문제를 내마. 이것을 풀면 저주이자 선물을 내리겠노라.
리치는 알 수 없는 소리를 하며 주문을 외웠습니다.
너의 물고기 주머니에 마법을 걸었으니 이제 그 속에서 무한정 물고기를 꺼낼 수 있다. 나는 무게 K를 제시할 테니, 무게 K를 정확히 만족하는 최소 물고기 수를 답하라
물고기들의 무게를 담은 배열이 주어질 때, 이를 조합하여 K를 만들 수 있는 최소의 물고기의 수를 구하세요.
제한 사항
- 배열 안에 들어있는 숫자는 1 이상 100 이하입니다.
- 1 < K < 1000
- 같은 무게의 물고기를 여러 번 써도 됩니다.
- K를 정확히 만들 수 없는 입력은 주어지지 않습니다.
- 1 ≤ 무게 배열의 길이 ≤ 10
입출력 예
| 무게 | K | 출력 |
|---|---|---|
| [45, 5, 3, 15] | 100 | 4 |
| [6, 2, 4, 8, 32] | 50 | 4 |
| [7, 2, 14, 28] | 74 | 5 |
입출력 설명
물고기의 무게가 담긴 배열을 입력받습니다. [45, 5, 3, 15]를 입력받는다면 100을 만족하는 무게의 조합 중 최소의 물고기가 필요한 조합은 45, 45, 5, 5로 총 4마리입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [[45, 5, 3, 15], 100] | 4 |
| 2 | [[6, 2, 4, 8, 32], 50] | 4 |
| 3 | [[7, 2, 14, 28], 74] | 5 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.