마법 구슬 찾기

시간 제한2초메모리 제한1024 MB

요약

구슬 k개와 마법 구슬 하나를 M개의 주머니에 나눠 담아, 0부터 N-1까지 모든 k에 대해 최악의 정리 비용을 최소화합니다.

문제

당신은 모양과 질량이 완전히 같은 $k+1$ 개의 구슬을 갖고 있다. 이 중 $k$ 개는 일반 구슬이고, 1개는 마법 구슬이다. 당신은 마법 구슬을 찾아 마법의 성에 들어가려고 한다.

마법 구슬과 일반 구슬을 육안으로 구별할 방법은 없다. 대신 마법 구슬을 찾아내는 데 사용할 수 있는 $M$ ( $M \ge 2$ )개의 주머니가 있다. 주머니에는 0부터 $M-1$ 까지 번호가 붙어 있다.

주머니를 활용해 마법 구슬을 찾는 방법은 다음과 같다.

갖고 있는 모든 구슬을 $M$ $M$ 개의 주머니에 나눠 담는다.
- 어떤 주머니에도 넣지 않은 구슬이 있으면 안 된다.
- 구슬을 담지 않은 빈 주머니는 있어도 된다.
- 주머니에는 구슬만 담을 수 있으며, 다른 주머니를 담을 수는 없다.
주문을 외운다.
주문을 외운 직후:
- 마법 구슬이 들어 있지 않은 주머니의 구슬은 모두 소멸된다.
- 마법 구슬이 들어 있는 주머니의 구슬은 마법 구슬의 보호를 받아 소멸되지 않는다. 다만 주문의 부수 효과를 수습해야 하고, 이 과정에서 비용이 든다. 마법 구슬이 $i$ 번 주머니에 있고 $i$ 번 주머니에 구슬이 $j$ 개 들어 있었다면, 비용은 $A\[i] \times j + B\[i]$ 원이다 ( $A\[i] \ge 0$ , $B\[i] \ge 1$ ).

마법 구슬은 절대 소멸되지 않으므로, 구슬이 마법 구슬 1개만 남을 때까지 위 과정을 반복하면 마법 구슬을 찾을 수 있다.

최악의 경우에 마법 구슬을 찾는 데 드는 비용을 최소화하려고 한다. 즉, $k+1$ 개의 구슬 중 어느 구슬이 마법 구슬이더라도 총 $w$ 원 이하를 들여 마법 구슬을 찾을 수 있는 최소의 $w$ 를 구하라.

$0$ 이상 $N-1$ 이하의 모든 $k$ 에 대해 이 문제를 해결하는 함수를 작성하라.