[C++] 28774번 Шестизначные документы

 

 

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

---

 

25/01/02

 

 

백준 땅따먹기에서 나온 문제 중 하나인데, 내가 풀었을 당시에는 골드 4였으나 골드 4치고는 굉장히 어렵다고 느꼈던 문제였다.

 

이러한 아이디어를 복습해보고자 글을 적어본다.

---

 

문제 접근 방식:

 

 

일단 문제가 러시아어로 적혀있기 때문에 번역을 하면 다음과 같다.

 

회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.
그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.
역전(inversion)이란, 두 번호 $i$와 $j$($i < j$)에 대해 $a_i$와 $a_j$의 $k$번째 자리 숫자에서 $a_i$의 $k$번째 숫자가 $a_j$의 $k$번째 숫자보다 클 때 발생하는 경우를 말합니다.
배열 ${a_i}$의 복잡성(complexity)은 여섯 자리 각각에서 발생하는 모든 역전의 총합으로 정의됩니다.
발레리는 식별자 세트의 복잡성이 낮을수록 주소창에 입력하는 데 걸리는 시간이 적게 든다는 것을 알고 있습니다.
문서 세트가 고정되어 있고, 검토 순서를 크게 변경하는 것은 위험할 수 있으므로(일부 문서를 누락할 가능성이 있음), 발레리가 사용할 수 있는 유일한 방법은 순서를 순환적으로 몇 자리 이동시키는 것입니다.
순환적 이동이란 배열 $a_1, a_2, \ldots, a_n$을 $t$칸 왼쪽으로 이동시키는 것으로, 이는 배열 $a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$를 의미합니다.
발레리가 주어진 배열의 복잡성을 최소화하는 순환 이동을 선택할 수 있도록 도와주세요.

 

입력 형식은 다음과 같이 주어진다.

3
277659
177013
314836

 

6자리 수 하나가 $a_i$가 되는 것이고, Complexity를 계산할 때는 각 자리 별로 Inversion의 개수를 센 후 다 더해주면 된다.

 

당연히 생각해볼 수 있는 것은, 각 자리 별로 독립이기 때문에 각 자리 별로 쪼개어 생각해볼 수 있다.

 

그래서 하나의 배열에 대해서 생각해보자.

 

즉, 위의 입력 예제의 예시라면 첫번째 자리만 모은 배열 $[2, 1, 3]$을 생각해보자는 뜻이다.

 

이제 우리는 고정된 하나의 배열에 대해서 Inversion의 개수를 빠르게 구하는 방법을 먼저 생각해봐야한다.

 

배열의 최대 길이 $N$은 $100 \ 000$으로 제한되어 있기 때문에 하나의 배열을 나이브하게 탐색하며 Inversion을 구하는 $\mathcal{O}(N^2)$방법은 통하지 않는다.

 

따라서 고정된 하나의 배열에 대해서 Inversion의 개수를 $\mathcal{O}(N)$으로 구해야 한다. 이는 counting sort의 기법을 사용하면 해결할 수 있다.

 

 

예를 들어, 하나의 배열이 다음과 같이 주어져 있다고 가정해보자.

 

$$[1, 2, 1, 3, 5, 2, 1, 3, 9, 7, 6]$$

 

그리고 지금까지 숫자 $i$가 몇 번 나왔는가를 나타내는 Count[10]배열을 선언하자.

 

그리고 다음과 같은 작업을 반복 수행해주면 된다.

 

$j$번째 배열의 원소 $d_j$를 볼 때, Count배열에 $d_j$보다 큰 숫자가 몇 번 나왔는가를 확인한다. 그 값을 Inversion 개수에 더해주고, $\text{Count}[d_j]$++를 해준다.

 

왜냐하면, 지금까지 본 배열의 원소는 $d_1$부터 $d_{j-1}$까지인데, 지금까지 본 배열의 원소 중에서 $d_j$로 인해 만들어 질 수 있는 Inversion은 $d_j$가 작고, $d_j$이전의 원소가 더 커야하기 때문이다. 따라서 Count배열을 선언하고 Inversion개수를 더해주는 것이다.

 

이 과정의 시간 복잡도는 $\mathcal{O}(10N) = \mathcal{O}(N)$이 소요된다.

 

 

이제 고정된 하나의 배열에 대해서 $\mathcal{O}(N)$의 시복도로 구할 수 있음을 확인했다.

 

근데, 우리는 모든 순환 이동에 대해서 이를 구해야 한다. 당연히, 이걸 그대로 하려면 $\mathcal{O}(N^2)$의 시간 복잡도가 소요되므로, 우리는 위에서 Count배열을 선언하여 시간 복잡도를 줄인 것 처럼, 시간 복잡도를 줄이는 방법을 한 번 더 생각해봐야 한다.

 

그래서 자연스럽게 떠오르는 방식은, 맨 처음의 배열에 대한 Inversion의 개수를 구하고, 한 칸 순환시킬 때마다 직접 계산하는 것이 아니라 "차이"를 더하고 빼줘서 빠르게 구해보는 방식이다.

 

그러면 "어떻게 구할 것인가?"가 문제가 될 것이다.

 

기존 배열 $[d_1, d_2, \dots , d_n]$이 주어져 있고, 이 배열에 대한 Inversion 개수를 위의 방식처럼 구했다고 해보자.

 

그러면, $[d_2, d_3, \dots , d_n, d_1]$일 때의 Inversion개수를 구해보자.

 

$d_1$이 맨 앞에 있었는데 사라졌다. 기존에 $d_1$이 맨 앞에 있음으로써 기여했었던 Inversion의 개수는 $d_2, d_3, \dots, d_n$중 $d_1$보다 작았던 원소의 개수와 같다.

 

이는 기존 배열의 Inversion을 구하면서 생긴 Count배열로 빠르게 구할 수 있다. 최종적으로 나온 Count배열을 통해 $d_1$보다 작은 원소의 개수를 빠르게 구할 수 있기 때문이다.

 

마찬가지로, $d_1$을 뒤에서 추가한다고 생각해보자. $d_2, d_3, \dots, d_n$ 중 $d_1$보다 큰 원소들과 $d_1$이 만남으로써 Inversion의 개수가 그만큼 늘어나므로, $d_2, d_3, \dots, d_n$중 $d_1$보다 큰 원소의 개수만큼 Inversion의 개수가 늘어난다.

 

따라서, 왼쪽으로 한 칸 순환시킬 때, 다음과 같이 Inversion의 개수가 늘어나고 줄어든다.

 

$$- \sum_{0}^{d_1 - 1} \text{Count} [i] + \sum_{d_1 + 1}^{9} \text{Count} [i]$$

 

이는 맨 처음 Inversion을 세었을 때 나왔던 Count배열로 빠르게 구할 수 있으므로, $\mathcal{O}(1)$만에 구할 수 있다.

 

이걸 $N$번 반복하면, 모든 순환의 Inversion 개수를 $\mathcal{O}(N)$만에 구할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 28774번 Шестизначные документы
// 누적 합, DP
/*
번역:
회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.
그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.

**역전(inversion)**이란, 두 번호 $i$와 $j$($i < j$)에 대해 $a_i$와 $a_j$의 $k$번째 자리 숫자에서 $a_i$의 $k$번째 숫자가 $a_j$의 $k$번째 숫자보다 클 때 발생하는 경우를 말합니다.
배열 ${a_i}$의 **복잡성(complexity)**은 여섯 자리 각각에서 발생하는 모든 역전의 총합으로 정의됩니다.

발레리는 식별자 세트의 복잡성이 낮을수록 주소창에 입력하는 데 걸리는 시간이 적게 든다는 것을 알고 있습니다.
문서 세트가 고정되어 있고, 검토 순서를 크게 변경하는 것은 위험할 수 있으므로(일부 문서를 누락할 가능성이 있음), 발레리가 사용할 수 있는 유일한 방법은 순서를 순환적으로 몇 자리 이동시키는 것입니다.
순환적 이동이란 배열 $a_1, a_2, \ldots, a_n$을 $t$칸 왼쪽으로 이동시키는 것으로, 이는 배열 $a_{t+1}, a_{t+2}, \ldots, a_n, a_1, a_2, \ldots, a_t$를 의미합니다.

발레리가 주어진 배열의 복잡성을 최소화하는 순환 이동을 선택할 수 있도록 도와주세요.

접근 방법:
일단 각 자리 별로 독립이므로 각 자리별로 다 쪼개자.
하나의 자리에 대해서 생각을 해보자.
우리는 이 자리의 모든 역전을 나이브하게 구하려면 O(N^2)의 시복도가 소요됨을 알고있다.
이걸 누적합을 사용하여 O(N)으로 줄여보자.
예를 들어, 하나의 자리에 대해서 복잡성을 계산하는데 이 자리가 다음과 같이 있다고 해보자.
1 2 1 3 5 2 1 3 9 7 6

그리고 숫자가 지금까지 몇번 나왔는가를 나타내는 Count배열을 선언해.
int Count[10] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

1. 처음에 1을 확인해. Count배열에 1보다 큰 숫자가 몇번 나왔는가를 모두 더해. 그 값은 0이야.
Count[1] += 1을 해줘.
Count = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

2. 2를 확인해. Count배열에 2보다 큰 숫자가 몇번 나왔는가를 확인해. 그 값은 0이야.
Count[2] += 1을 해줘.
Count = [0, 1, 1, 0, 0, 0, 0, 0, 0, 0]

3. 1을 확인해. Count배열에 1보다 큰 숫자가 몇번 나왔는가를 확인해. 그 값은 1이야.
Count[1] += 1을 해줘.
Count = [0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
...
이런 식으로 하나의 순환에 대해서 O(N)의 시복도로 구할 수 있다.

당연히 모든 순환에 대해서 하면 O(N^2)인데, 이러면 시간초과가 나므로 DP를 사용하여 계산해보자.

근데 이게 왜 골드임ㄷㄷㄷ
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ll;

vector<ll> solve(const vector<int>& A){
    vector<ll> ans;
    vector<int> cnt(10, 0);
    ll a = 0;
    // 초기 count구하기
    for (int i = 0; i < A.size(); i++){
        for (int j = A[i]+1; j < 10; j++){
            a += cnt[j];
        }
        cnt[A[i]]++;
    }
    ans.push_back(a);
    vector<int> cnt_accum(11, 0);
    cnt_accum[0] = cnt[0];
    for (int i = 1; i < 11; i++){
        cnt_accum[i] = cnt_accum[i-1]+cnt[i-1];
    }
    // 이후 ans 구하기
    for (int i = 0; i < A.size()-1; i++){
        a -= (ll)(cnt_accum[A[i]] - cnt_accum[0]); 
        a += (ll)(cnt_accum[10] - cnt_accum[A[i]+1]);
        ans.push_back(a);
    }
    return ans;
}

int main(void){
    int N; cin >> N;
    vector<vector<int>> A(6);
    vector<vector<ll>> ans(6);
    string S;
    for (int i = 0; i < N; i++){
        cin >> S;
        for (int j = 0; j < 6; j++){
            A[j].push_back((int)(S[j]-'0'));
        }
    }
    for (int i = 0; i < 6; i++){
        ans[i] = solve(A[i]);
    }
    ll m = 1'000'000'000'000'000'000;
    ll s = 0;
    for (int i = 0; i < N; i++){
        s = 0;
        for (int j = 0; j < 6; j++){
            s += ans[j][i];
        }
        m = min(m, s);
    }
    cout << m;
    return 0;
}