은행에 $m$장의 지폐가 있다. 각 지폐의 가치는 $b_1, b_2, \cdots, b_m$이다. 이 지폐들을 가지고 $n$명의 사람들에게 각각 $a_1, a_2, \cdots, a_n$만큼의 돈을 지급할 수 있는지 판별하시오.

  • $1 \le m, n \le 20$
  • $1 \le a_i, b_i \le 1000$

접근

일단 문제를 보면 냅색을 해야 하나? 하는 생각이 든다. 하지만 $m$과 $n$이 매우 작기 때문에 그냥 $2^m$개의 부분집합을 모두 보는 것으로도 충분하다. 그런데 $a_i$를 만들 수 있는 ${b_i}$의 부분집합의 개수는 최대 $_20 C _10 \approx 180,000$이기 때문에, 예를 들어 앞의 $i-1$명에게 지급한 지폐의 부분집합들과 $i$번째 사람에게 지급할 지폐의 부분집합들을 모두 조합하여 시도하는 방법은 TLE를 피할 수 없다.

제한이 제한이기 때문에 가능한 지폐의 $2^m$가지 부분집합을 노드로 갖는 그래프를 생각해 본다.

지폐를 받을 사람들의 순서를 고정해 놓으면 주어진 노드에서 다음으로 지폐를 받아야 할 사람이 고정된다. 그 사람을 $k$번째라고 하면, 지폐의 값의 합은 $\sum_{i=1}^{k-1}{a_i}$ 이상 $\sum_{i=1}^{k}{a_i}$ 미만이어야 한다. 반대로 말하면 지폐의 값의 합이 $a_i$의 누적합에서 어느 구간에 떨어지는지를 보고 $k$를 구할 수 있다. 그리고 $k$번째 사람이 받은 지폐의 합이 $a_k$를 초과하면 안되므로, 그렇지 않은 경우에만 다음 집합으로 엣지를 연결해 준다. $b_i$의 총합이 $a_i$의 총합보다 큰 경우 이미 모든 사람이 원하는 값만큼을 받은 상태일 수 있는데, 이때는 그냥 가능한 모든 다음 노드로 연결해주면 된다.

이렇게 그래프를 구성하고 공집합에서 전체집합으로 가는 경로가 존재하면 답은 YES, 아니면 NO다. 증명은 그렇게 어렵지 않다.

  • 경로가 존재하면 답은 YES

$a_i$의 누적합의 각 구간에서 다음 구간으로 진입하기 위해서는 그 경계값을 지폐의 합으로 갖는 노드를 반드시 거쳐야 한다. 모든 경계에 해당하는 노드를 나열하고, 이웃한 노드 간의 차집합에 해당하는 지폐들을 각 사람에게 주면 된다.

  • 답이 YES면 경로가 존재

답이 YES라는 것은 각 사람에게 지폐를 적절히 나눠주는 방법이 존재한다는 뜻이다. 그러면 각 사람에게 주어야 할 지폐들을 일렬로 나열하고, 남는 지폐가 있으면 마지막에 나열한 후 순서대로 지폐의 집합에 하나씩 추가하면 그래프 상의 하나의 경로를 얻는다.

따라서 경로의 존재성과 정답 사이에 if-and-only-if 관계가 성립한다.

구현

이 그래프는 DAG이므로 부분집합 원소 추가 그래프 상에서의 DAG DP = 비트DP로 풀 수 있다.

각 노드를 비트 형식으로 순회하면서 가능한 다음 노드로 가는 엣지가 있는지를 그때그때 판별해 가면서 boolean 값을 전이해 주면 된다.