https://www.acmicpc.net/problem/14959
사전 지식
이 문제를 제대로 푸려면 다음 두 문제를 먼저 풀고 올 필요가 있다.
https://www.acmicpc.net/problem/16570
16570번: 앞뒤가 맞는 수열
수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계
www.acmicpc.net
https://www.acmicpc.net/problem/1305
1305번: 광고
세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광
www.acmicpc.net
풀이
수열의 앞부터 제거하는 것은 어려우므로 뒤집도록 하자. 그러면 KMP 알고리즘으로 수열의 중복 주기를 찾아낼 수 있다.
그러면 답은 간단하다. 각 인덱스에 대해 주기의 마지막이라 가정하고 k + p의 최솟값을 구하면 된다.
가령 현재 인덱스가 i라고 하면 k는 n - (i + 1)이 된다. i + 1개의 원소를 제외한 원소를 삭제하기 때문이다. 그리고 p는 (i + 1) - fail(i)가 된다. fail(i)를 빼서 겹치지 않는 주기를 구하는 것인데 이는 1305번 광고 문제를 통해 잘 알려져 있다.
위 계산을 통해 k + p의 최솟값을 찾아 출력하면 정답이다.
전체 코드
|
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#include "ext/rope"
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;
int n;
vector<int> pat;
vector<int> bake_pi(vector<int> &pt)
{
vector<int> pi(pt.size());
int j = 0;
for (int i = 1; i < pt.size(); i++)
{
while (j and pt[i] != pt[j]) j = pi[j - 1];
if (pt[i] == pt[j]) pi[i] = ++j;
}
return pi;
}
void solve()
{
cin >> n;
pat.resize(n);
for (int &i : pat) cin >> i;
reverse(pat.begin(), pat.end());
int k = 0;
int p = 0;
int total = 1e9;
auto pi = bake_pi(pat);
for (int i = 0; i < pi.size(); i++)
{
int kk = pi.size() - (i + 1);
int pp = (i + 1) - pi[i];
if (kk + pp < total)
{
total = kk + pp;
k = kk, p = pp;
}
}
cout << k << " " << p;
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
제출 기록
'백준 > 문자열' 카테고리의 다른 글
| 백준 1498 - 주기문 (0) | 2022.07.22 |
|---|---|
| [ICPC] 백준 10266 - 시계 사진들 (0) | 2022.07.15 |
| [ICPC] 백준 9081 - 단어 맞추기 (0) | 2021.11.09 |
