[BOJ] 19073. Subsequence Sums

문제 링크

양의 정수로 이루어진 길이가 $n$인 수열 $A_{1}, \cdots , A_{n}$이 있습니다. 그리고 모든 요소의 합이 $i$인 $A$의 부분 수열의 갯수를 $B_{i}$로 하는 수열 $B$가 있습니다. 우리의 목표는 수열 $B$를 통해서 $A$를 만들면 되는데 사전순으로 가장 앞에오는 수열을 구해야 합니다.

먼저, 수열 $A$의 요소들 중 최솟값은 쉽게 구할 수 있습니다. $B_{a} > 0$이고 $B_{1} = \cdots = B_{a-1} = 0$이라면 최솟값은 $a$이 됩니다.

만약에 최솟값 요소를 포함하는 모든 부분 수열들을 수열 $B$에서 제거할 수 있다면 그 다음 작은 요소, 그 다음 작은 요소 순으로 $A$의 요소를 하나 하나 찾아갈 수 있고 이를 $n$번 반복하면 $A$를 완성할 수 있습니다.

그럼 최솟값 요소를 포함하는 모든 부분 수열들을 수열 $B$에서 어떻게 제거할 수 있을까요? 이건 아래와 같은 방법으로 할 수 있습니다.

1. $B_{a}$를 $1$ 감소시킵니다.
2. 다음 과정을 $a \leq i \leq m$인 $i$에 대하여 값이 증가하는 순서대로 수행합니다.
   2-1. $B_{i} > 0$이라면 $B_{i+a}$를 $B_{i}$ 감소시킵니다. $a$를 포함하지않은 부분 수열들 중 합이 $i$인 부분 수열의 갯수가 $B_{i}$개이고 이 말은 즉, $a$를 포함하면서 합이 $i+a$인 부분 수열의 갯수가 $B_{i}$개라는것을 의미합니다. 그래서 $B_{i+a}$를 $B_{i}$ 감소시킵니다.

이렇게 하면 수열 $A$를 구할 수 있습니다. 하지만 정확히는 나올 수 있는 수열 중 하나를 구한 것이긴 합니다. 우리는 그 중 사전순으로 가장 작은 수열을 구해야 하는데 결론부터 말씀드리면 우리가 구한 수열 $A$가 사전순으로 가장 작은 수열이 맞습니다.

만약 사전순으로 더 작은 수열 $A'$이 있다고 가정해보겠습니다. 그럼 $1 \leq j < i$인 모든 양의 정수에 대하여 $A_{j} = A'_{j}$이고 $A_{i} > A'_{i}$인 정수 $i$가 존재합니다. 하지만 저희가 수열 $B$에서 최소 요소를 포함하는 부분 수열을 제거하는 과정을 살펴보면 이건 불가능하다는 것을 알 수 있습니다. 그래서 저희가 구한 수열 $A$가 사전순으로 가장 작은 수열임을 알 수 있습니다.

시간 복잡도는 $O(nm)$입니다.