[Algorithm] cpp 백준 14959번: Slot Machines

문제

링크: https://www.acmicpc.net/problem/14959
요약: 길이 \(n\)의 관측 수열 \(T[1..n]\)이 존재하며, 어떤 시점 \(k\) 이후에는 길이 \(p\)의 주기로 반복된다고 할 때, 조건을 만족하는 모든 \((k,p)\) 중 \(k+p\)가 최소가 되는 해(동률이면 \(p\)가 최소)를 구한다.
제한/스펙: \(1 \le n \le 10^6\), 각 값은 0..999999, 시간 2초, 메모리 512MB.

입력/출력 형식

1
2
3
4
5
6
입력
n
T[1] T[2] ... T[n]

출력
k p

예시

1
2
3
입력: 6
612534 3157 423 3157 423 3157
출력: 1 2

접근 개요

\(k\) 이후 부분수열 \(S=T[k+1..n]\)이 주기 \(p\)를 가진다는 것은, 문자열(수열) 의미에서 \(S\)의 period가 \(p\)라는 뜻이다. 즉 \(1 \le i \le |S|-p\)에 대해 \(S[i]=S[i+p]\).
모든 접미사에 대해 “최소 주기”를 알 수 있으면, 각 접미사 길이 \(L\)에 대한 후보 비용은 \(k+p = (n-L) + p_{min}\). 여기서 KMP 접두사함수 \(\pi\)의 성질로 \(p_{min} = L - \pi[L-1]\) 이므로 비용은 \(n - \pi[L-1]\)로 정리된다.
따라서 전체에서 \(\pi[L-1]\)이 최대가 되는 접미사를 고르면 \(k+p\)가 최소가 된다. 동률이면 \(p=L-\pi\)를 최소화하려면 \(L\)이 작은 쪽을 선택한다.
“접미사에 대한 \(\pi\)”를 얻기 위해 수열을 뒤집어(Reverse) 놓고, 뒤집힌 수열의 모든 prefix에 대해 KMP 접두사함수를 계산한다. 길이 \(L\) prefix의 \(\pi\) 값은 원래 수열 길이 \(L\) 접미사의 \(\pi\)와 동일하다.

알고리즘

수열 \(T\)를 뒤집어 \(R\) 생성
\(R\)에 대해 접두사함수 \(\pi\)를 O(n)으로 계산
모든 길이 \(L=1..n\)에 대해 \(b=\pi[L-1]\), 비용 \(n-b\)를 평가
- 최댓값 \(b\)를 갖는 \(L\)을 선택, 동률이면 \(L\) 최소를 선택
\(k = n - L\), \(p = L - b\) 출력

복잡도

시간: O(n)
공간: O(n)

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> r(n);
    for (int i = 0; i < n; ++i) r[i] = a[n - 1 - i];

    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && r[i] != r[j]) j = pi[j - 1];
        if (r[i] == r[j]) ++j;
        pi[i] = j;
    }

    int bestB = -1;
    int bestL = 1;
    for (int i = 0; i < n; ++i) {
        int L = i + 1;
        int b = pi[i];
        if (b > bestB || (b == bestB && L < bestL)) {
            bestB = b;
            bestL = L;
        }
    }

    int k = n - bestL;
    int p = bestL - max(bestB, 0);
    cout << k << ' ' << p << '\n';
    return 0;
}

구현 (Python)

 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
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    r = a[::-1]
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and r[i] != r[j]:
            j = pi[j - 1]
        if r[i] == r[j]:
            j += 1
        pi[i] = j

    bestB = -1
    bestL = 1
    for i in range(n):
        L = i + 1
        b = pi[i]
        if b > bestB or (b == bestB and L < bestL):
            bestB = b
            bestL = L

    k = n - bestL
    p = bestL - max(bestB, 0)
    print(k, p)

if __name__ == "__main__":
    solve()