본문 바로가기

알고리즘

(라이캣의 꿈-2) 리치를 무찌르자!

Best 20 · 19번Lv. 3동적 계획법

(라이캣의 꿈-2) 리치를 무찌르자!

해골왕 리치와 결투를 벌이는 캣

문제 설명

해골섬 주변에서 물고기를 잡던 캣은 거친 비바람을 만났습니다.

비바람이 너무 세서 집에 갈 수가 없다냥….

캣은 해골섬 해변에 배를 정박하고 하룻밤을 묵을 장소를 찾기 위해 해골섬 이곳저곳을 탐험하기 시작합니다. 해골섬에는 특이하게 여러 조각상이 널브러져 있었습니다. 그때 어디선가 스산한 목소리가 들려왔습니다.

누구냐, 산 자가 도달할 수 없는 곳에 도달한 자는…? 흥미롭구나, 꿈으로부터 도달하다니.

안갯속에서 망토를 입은 해골 한 마리가 둥둥 떠 다가왔습니다. 캣은 전설 하나가 기억났습니다. 오래전에, 신에게 저주받은 리치가 해골섬에 갇혀있으며 자신의 영역을 침범하는 고양이를 산 채로 돌로 만들어버린다는 전설이었습니다.

산 자가 들어올 수 없는 이곳에 들어온 욕심쟁이에게 욕심쟁이 문제를 내마. 이것을 풀면 저주이자 선물을 내리겠노라.

리치는 알 수 없는 소리를 하며 주문을 외웠습니다.

너의 물고기 주머니에 마법을 걸었으니 이제 그 속에서 무한정 물고기를 꺼낼 수 있다. 나는 무게 K를 제시할 테니, 무게 K를 정확히 만족하는 최소 물고기 수를 답하라

물고기들의 무게를 담은 배열이 주어질 때, 이를 조합하여 K를 만들 수 있는 최소의 물고기의 수를 구하세요.


제한 사항

  • 배열 안에 들어있는 숫자는 1 이상 100 이하입니다.
  • 1 < K < 1000
  • 같은 무게의 물고기를 여러 번 써도 됩니다.
  • K를 정확히 만들 수 없는 입력은 주어지지 않습니다.
  • 1 ≤ 무게 배열의 길이 ≤ 10

입출력 예

무게K출력
[45, 5, 3, 15]1004
[6, 2, 4, 8, 32]504
[7, 2, 14, 28]745

입출력 설명

물고기의 무게가 담긴 배열을 입력받습니다. [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개도 함께 채점해요.