BOJ 10350. 은행

문제 링크

 

엄청 유명한 수학 루비 문제인데, 난 수학에 자신이 없어서 딱히 건드려 본 적이 없었다. 오늘따라 루비를 풀어보고 싶어서 잡기 시작했다.

 

엄밀한 증명이나 풀이 위주로 적는다기보다는 생각의 흐름 위주로 기록을 남겨 보려고 한다.

예제 분석

일단 문제의 풀이에 대한 감이 전혀 잡히지 않아서 예제를 가지고 놀아 봤다. 간단한 랜덤화 시뮬레이션 코드를 짜서 시행의 선택에 따라 어떤 결과가 나오는지를 알아보았다. 다양한 방법으로 시행을 해 본 결과, 다음과 같은 두 가지 추측을 하게 되었다.

• 여러 가능한 시행 중 어떤 것을 선택하더라도, 모든 수를 $0$ 이상으로 만드는 데 필요한 시행 횟수가 같다.
• 어떤 방법으로 시행을 완성하더라도 최종 상태가 동일하다.

이 관찰을 통해 어떤 수열 $A$에 대해 이 문제의 답을 $f(A)$라는 함수로 정의할 때, $f(A)$는 어떤 배열 $A$의 불변량처럼 생각할 수 있고, $A$에서 가능한 모든 시행 뒤의 배열 $A'$에 대해 $f(A') = f(A) - 1$임을 알 수 있다. 이 문제는 $f(A)$를 어떻게 더 빠르게 계산하는지를 찾는 것과 같다.

 

여러 가지 상황을 나이브를 통해 시험해 보면 실제 시행 횟수는 최댓값이 $O(n^3 \max A)$ 정도의 범위에 있음을 추측할 수 있다.

누적합

현재 연산의 문제점은 다루기가 너무 힘들다는 것이다. 어떤 수 $a$, $-x$, $b$ $(x>0)$이 차례로 있을 때 이들을 각각 $a-x$, $x$, $b-x$로 바꿔야 하는데, 바뀌는 값들 사이의 규칙성을 찾기 어렵다. 이러한 경우 이 연산의 특징이 드러나도록 주어진 배열 $A$를 적당히 조정할 수 있다.

 

증명에 관계없이, 일단 위 분석에서 나온 사실을 그대로 "믿자". 그러면, 주어진 배열 $A$에 대해 누적합 $S$를 생각할 수 있다. $S_i = \sum_{1 \le j \le i} A_j$로 정의된다. 배열 $A$에서 시행을 할 때, $S$가 어떻게 변하는지를 알아보면 다음과 같다. 시행의 인덱스를 $x$라 할 때,

• $2 \le x \le n-1$인 경우: $A = [\cdots, A_{x-1}, A_{x}, A_{x+1}, \cdots]$가 $A'=[\cdots, A_{x-1}+A_x, -A_x, A_{x+1}+A_x]$로 바뀐다. 이를 바탕으로 $S$와 $S'$의 관계를 구하면 $S'=[\cdots, S_{x-1}+A_x, S_{x-1}, S_{x+1}, \cdots]$가 되므로 결과적으로 $S_{x-1}$과 $S_{x}$만 교환된다는 것을 알 수 있다.
• $x = 1$인 경우: $S_1$은 $-2A_1$만큼 증가하고, $S_2$부터 $S_{n-1}$까지는 $-A_1$만큼 증가한다.
• $x = n$인 경우: $S_1$부터 $S_{n-2}$까지는 $A_n$만큼 증가하고 (실질적으로 값은 감소), $S_{n-1}$은 $2A_n$만큼 증가한다.

여기서 $2 \le x \le n-1$인 부분에 집중해 보자. 이 부분에서 시행은 단순히 누적합의 두 값을 교환하는 효과만을 가지고 있음을 알 수 있다. 어떤 $A_x$에서 시행이 가능할 조건은 $A_x < 0$, 즉 $S_{x+1} > S_x$임을 나타낸다. 이 연산을 반복적으로 적용하면 결국 $S[1\dots {n-1}]$ 부분을 정렬하는 효과를 얻을 수 있음을 알 수 있다. ($S_n$은 항상 일정한 값이다.) 또한 이때 드는 시행의 횟수는 자명하게도 $S$의 $[1, n-1]$ 구간 내에 존재하는 inversion의 개수이다.

 

이 방식의 문제점 중 하나는 $S_{n}$이 소외된다는 것이다. 이는 어찌보면 당연한데, $S_{n}$이 바뀌는 것은 불가능하기 때문이다. 그러나 여기서 한 가지 트릭을 생각할 수 있다. $x=n$인 경우의 변화는 $S_{n-1}$과 $S_n$을 교환한 후 모든 수에 일정한 값을 더한 것과 같다. 따라서, 정렬 구간을 $[1 \dots n]$으로 늘린 뒤 $S_n$이 전체 합과 같도록 수열을 조정한다고 생각하면 조금 더 편하게 문제에 접근할 수 있다.

 

따라서, 다음과 같은 방식을 생각해볼 수 있다.

• 다음 과정을 반복한다. (이 과정을 누적합 정렬이라고 하자.)
  • $A$를 적당히 회전한다. (이래도 답에 영향을 주지 않는다.)
  • 누적합 $S$를 구하고, $S$의 inversion 개수를 구한 다음 이 부분을 정렬한다.
  • $S_n$이 $A$의 전체 합과 같도록 $S$ 전체에 특정 수를 더한다.
  • $S$의 difference array를 구해 변경된 $A$ 배열을 얻는다.

위 알고리즘은 최대 $O(n^2)$개의 시행을 $O(n \log n)$에 할 수 있으므로, 대략적으로 $O(n)$배 정도 빨라진 알고리즘이라고 생각할 수 있다. 그러나 이것으로는 여전히 시간 초과가 날 것이다. 위 알고리즘을 단순히 반복하지 말고, 추가적인 관찰을 해 보자.

 

누적합 정렬이 한 번 끝나면 배열 $A$는 어떤 형태가 되는가? $S$가 정렬되어 있으므로, $A_2$부터 $A_{n}$까지의 수는 모두 $0$ 이상이라는 것을 알 수 있다. 따라서 놀랍게도, 저 과정을 한 번 하게 되면 $A$의 음수는 최대 한 개로 줄어든다. 이 형태는 일반적인 형태보다 훨씬 생각하기 편리하다.

 

예를 들어, $A = [2, -1, -3, 4, 2, -5, 2]$라고 하자. $S = [2, 1, -2, 2, 4, -1, 1]$이 되고, 여기서 정렬을 하면 inversion $10$과 함께 $S'=[-2, -1, 1, 1, 2, 2, 4]$라는 결과를 얻는다. 전체 합은 $4$가 아닌 $1$이므로 이에 맞춰 $S'$에서 $3$씩 빼주고 역산해 $A'$를 얻으면 $A' = [-5, 1, 2, 0, 1, 0, 2]$이다.

 

이제 우리는 $A'$를 항상 음수가 하나인 상태로 만들 수 있다. 그렇다면, 음수가 하나인 상태에서 문제를 쉽게 풀 수 있을까?

 

일단 우리가 알 수 있는 것 한 가지는, 위에서 했던 방법을 그대로 반복하면 계속 문제를 해결할 수 있다는 것이다. 누적합 정렬을 하고 $A'$를 왼쪽으로 한 칸 회전시키는 과정을 반복해 계속 $A'$를 바꾸면, 다음과 같은 과정을 통해 바뀐다.

$A'$	$S'$	inversion	누적 inversion
$[-5, 1, 2, 0, 1, 0, 2]$	$[-5, -4, -2, -2, -1, -1, 1]$	10	10
$[-4, 1, 2, 0, 1, 0, 1]$	$[-4, -3, -1, -1, 0, 0, 1]$	6	16
$[-3, 1, 2, 0, 1, 0, 0]$	$[-3, -2, 0, 0, 1, 1, 1]$	4	20
$[-3, 1, 2, 0, 0, 1, 0]$	$[-3, -2, 0, 0, 0, 1, 1]$	2	22
$[-3, 1, 2, 0, 0, 0, 1]$	$[-3, -2, 0, 0, 0, 0, 1]$	2	24
$[-2, 1, 2, 0, 0, 0, 0]$	$[-2, -1, 1, 1, 1, 1, 1]$	2	26
$[-2, 1, 1, 1, 0, 0, 0]$	$[-2, -1, 0, 1, 1, 1, 1]$	2	28
$[-2, 1, 1, 0, 1, 0, 0]$	$[-2, -1, 0, 0, 1, 1, 1]$	2	30
$[-2, 1, 1, 0, 0, 1, 0]$	$[-2, -1, 0, 0, 0, 1, 1]$	2	32
$[-2, 1, 1, 0, 0, 0, 1]$	$[-2, -1, 0, 0, 0, 0, 1]$	2	34
$[-1, 1, 1, 0, 0, 0, 0]$	$[-1, 0, 1, 1, 1, 1, 1]$	2	36
$[-1, 1, 0, 1, 0, 0, 0]$	$[-1, 0, 0, 1, 1, 1, 1]$	1	37
$[-1, 1, 0, 0, 1, 0, 0]$	$[-1, 0, 0, 0, 1, 1, 1]$	1	38
$[-1, 1, 0, 0, 0, 1, 0]$	$[-1, 0, 0, 0, 0, 1, 1]$	1	39
$[-1, 1, 0, 0, 0, 0, 1]$	$[-1, 0, 0, 0, 0, 0, 1]$	1	40
$[0, 1, 0, 0, 0, 0, 0]$	$[0, 1, 1, 1, 1, 1, 1]$	1	41

 

위 과정이 일어나는 메커니즘은 다음과 같이 서술할 수 있다.

• $A_1$이 $0$ 이상이라면, 이미 전 과정이 끝났다. 여기서 프로세스를 종료한다.
• 그렇지 않다면, $A_2 + \cdots + A_l \ge -A_1$인 최소의 $l$을 찾는다. 이 단계에서 추가되는 inversion의 수는 $l-1$개이다.
• 이후 $A_l$을 $-A_1 - (A_2 + \cdots + A_{l-1})$과 $(A_2 + \cdots + A_l) - (-A_1)$의 두 값으로 쪼갠다. 그 뒤의 값은 인덱스가 하나씩 밀려난다.
• $A_1$에서는 기존의 $A_n$ 값 ($l=n$인 경우 변경 이전의 값)을 더한 값을 집어넣고, 앞에서 $A_l$을 쪼개면서 생겨난 $A_{n+1}$의 값을 소멸시킨다.

이 과정은 프로세스 종료까지 계속 반복될 것이다. 여기서, $l$을 기준으로 프로세스 실행 단계를 나눠서 생각한다면 조금 빠른 시간 복잡도에 처리할 수 있을 가능성이 보인다. 그리고 이는 실제로 가능하다.

 

간단하게 설명하면, 일단 우리의 목표는 $A_1$을 올려서 $A_2 + \cdots + A_{l-1} \ge -A_1$이 되게 하는 것이다. 그리고 $A_1$에서 제거할 수 있는 양은 $A_n, A_{n-1}, \cdots, A_{l+1}, (A_2 + \cdots + A_l) + (-A_1)$이 반복된다. 이 반복되는 $n-l+1$개의 양을 먼저 몇 번만큼 돌려가면서 뺄 수 있는지를 구해주고, 이만큼의 작업을 미리 해 준다. 마지막 반복은 나이브하게 한 턴씩 돌려주며 답을 구할 텐데, 이때 한 턴을 $O(1)$에 시뮬레이션할 수 있어야 한다. 하지만 방법은 간단하다. $A_{l+1}$부터 $A_n$까지의 부분을 큐에 넣고 돌려주면서 해결하면 된다. 이 마지막 부분에서의 턴 개수가 $O(n)$개 이하임이 보장되므로, 고정된 $l$마다 시뮬레이션을 $O(n)$에 마칠 수 있어 답을 $O(n^2)$에 구할 수 있다.

 

참고를 위해 코드를 첨부한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[10002], sum;

void firstStep();
void solve();

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]), sum += arr[i];

    /// 작은 케이스
    if(n==1 || *min_element(arr+1, arr+n+1) >= 0) {puts("0"); return 0;}
    if(n==2) {if(arr[1] >= 0 && arr[2] >= 0) puts("0"); else puts("1"); return 0;}

    /// 첫 번째 누적합 정렬
    firstStep();

    /// 그 뒤를 품
    solve();
}

ll A[10002], S[10002], V[10002];
ll ans;

void mergeSort(int l, int r){
    if(l==r) return;
    int m = (l+r)>>1;
    mergeSort(l, m);
    mergeSort(m+1, r);
    int i = l, j = m+1, k = l;
    for(; i<=m && j<=r; ){
        if(S[i] <= S[j]) V[k++] = S[i++];
        else V[k++] = S[j++], ans += (m-i+1);
    }
    while(i<=m) V[k++] = S[i++];
    while(j<=r) V[k++] = S[j++];
    for(i=l; i<=r; i++) S[i] = V[i];
}

void firstStep(){
    for(int i=1; i<=n; i++) A[i] = arr[i], S[i] = S[i-1] + A[i];
    mergeSort(1, n);
    for(int i=1; i<=n; i++) A[i] = S[i] - S[i-1];
    A[1] += sum - S[n];

    #ifdef TEST
    printf("inv: %lld\n", ans);
    for(int i=1; i<=n; i++) printf("%lld ", A[i]); puts("");
    for(int i=1; i<=n; i++) printf("%lld ", S[i]); puts("");
    #endif
}

ll que[30002];
int ql, qr;

void que_init(){
    ql = qr = 0;
}
void que_push(ll x){
    que[qr++] = x;
}
ll que_pop(){
    return que[ql++];
}

void solve(){
    while(A[1] < 0){
        S[1] = 0;
        for(int i=2; i<=n; i++) S[i] = S[i-1] + A[i];
        int l = 2;
        while(S[l] < -A[1]) l++; /// [2, l] 구간을 고려해야 함

        ll back_sum = (S[l] + A[1]);
        for(int i=l+1; i<=n; i++) back_sum += A[i];
        ll turns = max(0LL, (-A[1] - S[l-1]) / back_sum - 1);
        if(turns){
            ans += turns * (l-1) * (n-l+1), A[1] += turns * back_sum;
            A[l] -= turns * back_sum, S[l] -= turns * back_sum;
        }

        /// 이제 나이브하게 뒷부분 처리하기. 한 번의 연산을 O(1)에 해야 한다
        que_init();
        for(int i=n; i>l; i--) que_push(A[i]);
        while(S[l-1] < -A[1]){
            ll diff = (S[l] + A[1]);
            A[l] -= diff, S[l] -= diff;
            que_push(diff);
            A[1] += que_pop();
            ans += (l-1);
        }
        for(int i=n; i>l; i--) A[i] = que_pop();
    }

    printf("%lld", ans);
}

증명?

증명에 대해서는 하나도 아는 것이 없으며, 어떤 식으로 해야 할지 감도 못 잡았다. 난이도 기여에 적힌 내용 등을 합쳐서 추정해 보면 다음과 같이 생각할 수 있을 것 같다.

 

일단 위에서 생각했던 정보들은 누적합의 inversion을 찾는 것이다. 실제로 각 step은 모두 두 수를 교환하는 것에 대응되었으므로, 이러한 생각은 나름 일리가 있다. 그러나, inversion으로 설명할 수 없는 부분이 바로 $S_n$과 $S_1$ 사이의 관계였다.

 

이를 해결하기 위해 생각해야 하는 개념은 $A$를 무한히 연장한 수열의 inversion을 생각하는 것으로 보인다. 예를 들어, 위에서 사용한 케이스의 초기 상태 $A=[2, -1, -3, 4, 2, -5, 2]$에 대해 $S=[2, 1, -2, 2, 4, -1, 1]$이었다. 그런데 이 $A$를 무한히 반복한 수열 $A_\infty$를 생각해 보면 $S_\infty$ 역시 구할 수 있고, 이 수열의 초기 몇 항은

$$
S_\infty = [2, 1, -2, 2, 4, -1, 1; \quad 3, 2, -1, 3, 5, 0, 2; \quad 4, 3, 0, 4, 6, 1, 3; \quad 5, 4, 1, 5, 7, 2, 4; \cdots]
$$

와 같이 쓸 수 있다. 편의상 수열이 반복되는 자리마다 공백을 삽입하였다.

 

위에서 처리하지 못했던 한 가지 케이스인 $S_1$과 $S_n$를 바꾸는 과정은, 위 수열에서 단순히 $S_n$과 $S_{n+1}$을 바꾸는 것으로 생각할 수 있다. 또한 수열이 무한히 반복되고 있으므로, $S_i$와 $S_{i+1}$을 바꾸는 일이 필요할 때 $S_{i+n}$과 $S_{i+n+1}$이 같이 바뀐다고 생각해야 할 것이다. 이런 점을 고려할 때, 이 문제가 $S_\infty$에서 $1 \le i < j$이고 $i \le n$인 $(i, j)$ 중 $S_i > S_j$인 것의 개수를 세는 문제라는 직관을 얻을 수 있다.

 

엄밀한 증명은 다른 사람들의 글을 참고하면 좋을 것 같다.