[종만북] 문제: CHRISTMAS
문제
$n(1 \leq n \leq 100000)$개의 상자는 인형의 개수 $k(1 \leq k \leq 100000)$를 가지고 있습니다. 이는 $D[i] = k_i$으로 표현됩니다.
$1 \leq H \leq T \leq n$일 때, 문제 2개를 구해야 합니다.
- $\sum_{i = H}^T \bmod k = 0$을 만족하는 $(H, T)$의 경우의 수를 전부 구하시오.
- 문제 1의 경우의 수를 여러 개 택할 수 있고 상자끼리 겹치지 않을 때 최대 몇 개까지 택할 수 있는지 구하시오.
서론
부분합에 대해 알아봅시다.
부분합을 왜쓰나요
만약에 어떤 배열의 연속되는 원소의 합 $\sum_{i = m}^n list[i]$을 구한다고 쳤을 때, 이를 무지성 반복문을 통해 구할 수 있습니다. 그러면 $n - m + 1$번만큼 반복해야합니다.
단순히 이 합을 한 번만 쓴다면 큰 문제가 없습니다만… 만약 합을 여러 번 쓴다고 가정하면, $n - m + 1$을 여러 번 반복해야하니 좋지 않죠.
그래서! 여러 번 쓴다고 가정 했을 때 우리가 쓸 수 있는 테크닉이 있습니다.
먼저, $psum[n]$을 이렇게 정의합니다.
$psum[n] = \sum_{i = 0}^n list[i]$
$\sum_{i = m}^n list[i] = \sum_{i = 0}^n list[i] - \sum_{i = 0}^{m-1} list[i]$의 공식을 이용해서
$\sum_{i = m}^n list[i] = psum[n] - psum[m-1]$로 변환이 가능합니다.
따라서 $psum[0…n]$을 한번 구해 놓으면 $\sum_{i = m}^n list[i]$를 구하는 시간은 $O(1)$시간이 걸립니다. 이는 엄청난 이득입니다!!!
번외로, 부분 합이 update가 자주 일어나는 환경이라면, 세그먼트 트리를 이용해야 합니다. 이는 나중에 공부할 예정입니다.
알고리즘 구상
조건을 수식으로
앞서 설명한 개념을 이용해서 조건을 표현하는 방정식을 짭니다.
$(psum[T] - psum[H-1]) \bmod k = 0$을 만족하는 $(H,T)$를 찾기만 하면 됩니다만.. $n$은 100000dl 최댓값이므로
$\binom{100000 + 2 - 1}{2} = \text(50억)$… 이 50억개에 대해 경우의 수를 계산하면 컴퓨터가 오래 걸릴 것입니다.. 따라서 수식을 개선해야 합니다.
수식을 개선하기
$(psum[T] - psum[H-1]) \bmod k = 0$를
$psum[T] \bmod k = psum[H-1] \bmod k$로 개선이 가능합니다.
$psum[i]$$(0 \leq i \leq n)$의 정의를 이용해서 또 개선해봅시다. $k$로 나눈 나머지만이 중요하므로
$psum[i] = (\sum_{j = 0}^n D[j]) \bmod k$로 새롭게 정의 가능합니다.
그러면 $psum[i] = k’(0 \leq k’ < k)$의 값을 가지게 됩니다.
따라서 각 $k’$가 같은 $psum[i]$끼리 매칭.. 즉 두 개 이상 존재 시 두 개를 매칭해주면 됩니다.
한 가지 주의할 점은, 부분 합을 이용하기 때문에 $psum[0]$을 주의해야합니다. 구현 시에는 이를 주의하기 위해 $psum[1…n]$의 범위로 정의합니다.
문제 1
$f_i$ = 숫자 $i$가 $psum$에 출현하는 횟수로 정의하면
\[\sum_{j=0}^{k-1} \binom{f_j}{2} = \sum_{j=0}^{k-1} \frac{f_j (f_j - 1)}{2}\]이렇게 문제 1의 답을 구하는 식을 작성할 수 있습니다.
문제 2
문제 1을 만족하고 범위가 겹치지 않는 $(H,T)$를 많이 골라 봅시다.
완전 탐색 알고리즘으로 설계하여 재귀 함수를 작성하면, 이를 메모이제이션이 적용가능한 형태임을 파악 가능합니다.
따라서 다이나믹 프로그래밍을 이용해서 풀 수 있습니다.
먼저 Subproblem을 정의해봅시다.
$DP(i)$ = $i$까지 최대로 고를 수 있는 문제 1의 수로 정의합니다.
$DP(i)$에서 $i$번째 원소가 문제 1의 경우의 수들의 범위에 들어가는지/들어가지 않는지 구별해서 점화식을 작성 가능합니다.
$i$번째 원소를 고른다고 생각했을 때, $i$번째의 원소의 값과 같은 원소를 이전에 언제 골랐는지 저장할 배열이 필요합니다.
따라서 $prev[i]$를 선언하여 값을 저장합니다.
Subproblem을 $DP(i) = max(DP(i-1), DP(prev[i]) + 1)$로 정의합니다.
$prev[i]$는 $i-1$이하이므로. 각 Subproblem간의 의존성이 명확해
이를 이용해서 반복적 동적 계획법을 설계합니다.
알고리즘 설계
psum을 구하고,psum의 값이 몇 번 쓰이는지vector<int> count에 저장한다.- 이후
count를 이용해서 공식을 이용해 문제 1의 답을 구한다. - 현재 index 이전의
psum의 값을 마지막으로 방문한 index를 저장하는prev를 이용해 반복적 동적 계획법을 구현하여 문제 2의 답DP[n]를 구한다. - 2번과 3번 과정에서 얻은 답을 출력한다.
알고리즘 구현
main()
알고리즘 설계에 적힌 순서대로 코드를 구현합니다.
배열의 크기를 최적화하고 값을 초기화하기 편하게 vector를 이용합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int MOD = 20091101;
int n, k;
int D[100001], psum[100001];
int main() {
fastIO;
int T;
cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> D[i];
}
vector<long long> count(k, 0);
count[0] = 1;
for (int i = 1; i <= n; i++) {
psum[i] = (psum[i - 1] + D[i]) % k;
count[psum[i]]++;
}
int ret = 0;
for (int i = 0; i < k; i++) {
if (count[i] >= 2)
ret = (ret + ((count[i] * (count[i] - 1)) / 2)) % MOD;
}
vector<int> DP(n + 1, 0);
vector<int> prev(k, -1);
prev[0] = 0;
for (int i = 1; i <= n; i++) {
int &cache = prev[psum[i]];
DP[i] = DP[i - 1];
if (cache != -1 && DP[i] < DP[cache] + 1) {
DP[i] = DP[cache] + 1;
}
cache = i;
}
cout << ret << " " << DP[n] << endl;
}
return 0;
}
최종 코드
여기에서 확인하세요!