BOJ 24502 - blobsad [C++]

 

https://www.acmicpc.net/problem/24502

24502번: blobsad

문제 요약

길이 $N$인 수열 $A$와 양의 정수 $K$가 주어진다.

이 수열에 작업을 할 수 있다.

• 어떤 $i$에 대해, $A_i$를 1 줄이고 $A_{i-1}$ 혹은 $A_{i+1}$을 1 올린다.

모든 $i$에 대해 $A_i$가 $K$의 배수가 되도록 만들 때, 작업 횟수의 최솟값을 구하는 문제이다.

 

문제 해결

문제 $A_i$가 $K$의 배수인가를 결정짓는 요소는 $A_i \bmod{K}$이다. 따라서, 주어진 모든 $A_i$를 $A_i \bmod{K}$로 바꿔서 생각한다.

 

첫 칸부터 탐색하며 누적 합이 $K$ 이상이 되는 순간, 그 구간 내에 $K$를 전부 몰아넣어야 한다.

구간이 $[l, r]$이라고 하자.

$S_i$를 이 구간 내의 블롭 $K$개가 모두 $i$번째에 모였을 때의 작업 횟수로 정의하면,

$S_l = A_{l+1} + 2A_{l+2} + \cdots + (r-l)A_r$,

$S_{l+1} = A_l + A_{l+2} + \cdots + (r-l-1)A_r$,

$\vdots$

$S_r = (r-l)A_l + (r-l-1)A_{l+1} + \cdots + A_{r-1}$

이다.

각 $S_i$는 위의 식에 누적 합을 이용하면 빠르게 구할 수 있다.

 

$\sum \limits_{i=l}^{r} {A_i}$가 $K$로 나누어떨어지지 않는다면, 그 나머지만큼 $A_r$의 값이 남아있게 됨에 주의해야 한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll N, K;
    cin >> N >> K;
    ll arr[1000000]{}, s = 0;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        arr[i] %= K;
        s += arr[i];
    }
    if (s % K) { cout << "blobsad"; return 0; }

    ll ans = 0, pos = 0, S1 = 0, S2 = 0, S3 = 0, cnt = 0;
    for (int i = 0; i < N; i++) {
        S1 += (cnt++) * arr[i];
        S2 += arr[i];
        if (S2 >= K) {
            S1 -= (cnt - 1) * (S2 - K);
            ll mn = S1, id = pos++;
            for (; pos <= i; pos++) {
                S3 += 2 * arr[pos - 1];
                S1 = S1 - K + S3;
                if (S1 < mn)	mn = S1, id = pos;
            }
            ans += mn;
            arr[i] = 0;

            if (S2 % K) {
                arr[i] = S2 % K;
                pos--;
                S2 = arr[i];
                S1 = 0, S3 = 0, cnt = 1;
            }
            else {
                S1 = 0, S2 = 0, S3 = 0, cnt = 0;
            }

        }
    }
    cout << ans;


}