ABC 159F: Knapsack for All Segments

Link

• https://atcoder.jp/contest/abc159/tasks/abc159_f

• AtCoder Beginner Contest 159 F

Tag

• dp

Time Complexity

• $O(NS)$

길이 N인 수열과 정수 S가 주어진다. $f(L, R)$ 은 수열에서 L이상 R이하 인덱스로 만들수 있는 합이 S인 부분집합의 갯수로 정의된다. 이때 모든 $(L, R)$ 쌍에 대해 $f(L, R)$의 합을 구해야 한다.

 

일단 $L = 1$로 고정했다고 생각해보자. $dp[i][j]$ := (1 ~ i)까지 선택해서 합이 j가 되는 경우의 수 로 정의하면, 냅색처럼 $O(NS)$에 dp 배열을 채울 수 있다. 이때 초기값으로 $dp[i][0] = 1$로 했을 것이다. $L = 2, 3, ... , R$ 에 대해서는 어떻게 하면 될까.

 

$L = i$에 대해 dp배열을 계산한다고 하면, $A_{1}, A_{2}, ... , A_{i-1}$은 배제된다. 그리고 $A_{i}$ 부터 dp 계산에 들어갈 텐데, 그 뒤부터는 연속적으로 이전과 같다. 따라서 그 이전 값의 합이 0이라고 생각하고 dp 계산은 똑같이 진행해 주면 되고, $dp[0] = i$ 주고 계산하는 것과 같다.

 

이제 $dp[i][j]$ := (L ~ i)까지 선택해서 합이 j가 되는 경우의 수의 합 (1 ≤ L ≤ i) 로 정의하면, $dp[i][0] = i$ 로 기저 case 설정 후 똑같이 dp를 계산하면 되고, 시간복잡도는 그대로 $O(NS)$다. 또, 슬라이딩 윈도우나 계산 순서를 잘 바꿔주면 공간복잡도를 $O(N)$로 줄일 수 있다.

Code