취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16900번 문제인 이름 정하기이다.
문제는 아래 링크를 확인하자.

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

K=1인 경우 S를 그대로 출력해야 함은 자명하다.

K=2인 경우 S 위에 또다른 S를 최대한 겹치게(단, 완전히 일치하지는 않게) 배치하는 방법을 생각해보자. 그렇게 겹쳐 완성한 문자열은 prefix와 suffix가 모두 S여야 한다는 점에 초점을 맞춰보면 S 위의 어떤 인덱스 i에 대하여 S의 부분문자열 S[i..]가 S의 prefix가 되는 위치에서 이어쓰는 것이 문제에서 구하는 답의 후보가 됨을 알 수 있다. 이러한 i가 존재한다면 그중 가장 작은 i를 찾는 것으로 답을 찾을 수 있다. 그렇지 않다면 단순하게 S를 뒤에 이어쓰는 것이 답이 될 것이다. 

위의 i의 값들은 모든 i에 대하여 S와 S[i..]의 가장 긴 공통 접두사의 길이를 구하는 알고리즘인 Z 알고리즘을 이용해 구할 수 있다.

K>2인 경우, K-1의 답의 S와 같은 크기의 suffix(=S)에 K=2인 경우와 같은 방식으로 문자열을 이어붙여나가는 것으로 문제를 해결할 수 있다. 이 과정의 규칙을 찾아 수식을 세워 문제를 해결할 수도 있다.

문제의 답이 32비트 정수 범위를 넘을 수 있음에 유의해 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int N, R;
string s;
int Z[500001];
int k;
int prd;

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

    cin >> s >> R;
    N = prd = s.length();
    s += '$';

    for (int i = 1; i < N; i++) {
        int& val = Z[i];
        if (i < k + Z[k]) val = min(Z[i - k], k + Z[k] - i);
        while (s[val] == s[i + val]) val++;

        if (k + Z[k] < i + Z[i]) k = i;

        if (i + Z[i] == N) {
            prd = i;
            break;
        }
    }

    cout << (ll)N + (ll)prd * (ll)(R - 1);
}