[백준][C++] 4206번 피보나치 단어 (dp, kmp)

1. 문제

4206번: 피보나치 단어 (acmicpc.net)

 

 

2. 간단 풀이

이 문제는 입력의 크기를 제외하면 단순하다. 

 

fib[i] = fib[i-1] + fib[i-2] + mid

 

이 공식을 사용하여 중간에 걸친부분을 조사하여 새로운 패턴이 생기는지 확인만하면된다.

 

하지만 long long 타입의 크기의 문자열을 처리해야한다는것.

 

이를 그대로 처리하게되면 당연히 시간 초과 메모리 초과가 일어날것은 뻔하다.

 

그러므로 피보나치의 성질을 활용하여 다루는 문자열의 크기를 제한하고, kmp알고리즘을 사용하여 

 

효율적으로 처리해야한다.

 

 

 

3. 풀이

피보나치 문자열이 일단 패턴보다 길어야 패턴이 보인다는것은 자명하다.

 

길이가 같거나 더 긴 첫번째 피보나치 문자열을 first 라고하고 다음 문자열을 second라하자

 

그러면 다음과 같은 규칙을 볼 수 있을것이다.

(줄여서 f, 그다음 피보나치 문자열은 s라고해보자)

 

1 = f

2 = s

3 = s + f   ... sf

4 = sf + s  ... fs

5 = sfs + sf  ... ss

6 = sfssf + sfs ... fs

7 = sfssfsfs + sfssf ... ss

 

3 번째를 제외하면 중간에 걸친 문자열은 두가지 문자열이 반복되는것을 볼 수 있다.

 

또한 패턴의 길이랑 같거나 큰 f 이므로 이 중간의 걸친 문자열보다 범위를 다음과 같이 더 줄일 수 있다.

 

void init_mid()
{
    ull fs = tmpstr[1].size() - p.size() + 1;
    ull bs = tmpstr[0].size() - p.size() + 1;
    ull w = p.size() * 2 - 2;

    m_[0] = (tmpstr[1] + tmpstr[0]).substr(fs, w);    // 처음
    m_[1] = (tmpstr[0] + tmpstr[1]).substr(bs, w);    // 홀수번 문자열
    m_[2] = (tmpstr[1] + tmpstr[1]).substr(fs, w);    // 짝수번 문자열
}

 

그리고  아래와 같이 중간부분에서 새로 생기는 패턴을 찾는 dp 재귀함수를 짜서

 

전체 개수를 구할 수 있다.

 

(당연히 그 전에 first와 second 에도 kmp함수를 사용하여 패턴의 개수를 찾아줘야한다.)

 

ull cached[111];
ull F(int i, int count)
{
    if (i > n)
    {
        return cached[i - 1];
    }
    string *mid{nullptr};

    if (count == 0)
    {
        mid = &m_[0];
    }
    else if (count % 2 == 1)
    {
        mid = &m_[1];
    }
    else if (count % 2 == 0)
    {
        mid = &m_[2];
    }

    ull isFind = 0;

    if (p.size() > 1)
    {
        isFind = kmpSearch(*mid, p, fail);
    }

    cached[i] = cached[i - 1] + cached[i - 2] + isFind;

    return F(i + 1, count + 1);
}

 

 

 

 

4. 전체 코드

 

주어진 N이 first 피보나치 문자열 의 피보나치 번호(인덱스 i)보다 작을 경우

 

이 경우 0 을 반환하게 해줘야한다.

 

또한 이코드에서 i+2 부터 dp 함수를 실행하므로

 

i+2 가 n 보다 커서 바로 함수가 종료되는경우

 

i+1 이나 i 가 n 인지 확인하여 적절한 답을 리턴해줘야한다.

 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
// 9
using namespace std;

using ull = unsigned long long;

const string first = "0";
const string second = "1";
int n;
string p; // 100,000

string tmpstr[2];
string m_[3];
void failure(const string &B, vector<long long> &fail);
ull kmpSearch(const string &A, const string &B, vector<long long> &fail);

vector<long long> fail;

ull cached[111];
ull F(int i, int count)
{
    if (i > n)
    {
        return cached[i - 1];
    }
    string *mid{nullptr};

    if (count == 0)
    {
        mid = &m_[0];
    }
    else if (count % 2 == 1)
    {
        mid = &m_[1];
    }
    else if (count % 2 == 0)
    {
        mid = &m_[2];
    }

    ull isFind = 0;

    if (p.size() > 1)
    {
        isFind = kmpSearch(*mid, p, fail);
    }

    cached[i] = cached[i - 1] + cached[i - 2] + isFind;

    return F(i + 1, count + 1);
}

void init_mid()
{
    ull fs = tmpstr[1].size() - p.size() + 1;
    ull bs = tmpstr[0].size() - p.size() + 1;
    ull w = p.size() * 2 - 2;

    m_[0] = (tmpstr[1] + tmpstr[0]).substr(fs, w);
    m_[1] = (tmpstr[0] + tmpstr[1]).substr(bs, w);
    m_[2] = (tmpstr[1] + tmpstr[1]).substr(fs, w);
}

ull solve()
{
    tmpstr[0] = first;
    tmpstr[1] = second;
    failure(p, fail);
    int i = 0;
    while (tmpstr[0].size() < p.size())
    {
        i++;
        string tmp = tmpstr[1] + tmpstr[0];
        tmpstr[0] = tmpstr[1];
        tmpstr[1] = tmp;
    }    
    if (n < i)
    {
        return 0;
    }
    ull b_c = kmpSearch(tmpstr[0], p, fail);
    if (b_c != 0)
    {
        cached[i] = b_c;
    }

    ull f_c = kmpSearch(tmpstr[1], p, fail);
    if (f_c != 0)
    {
        cached[i + 1] = f_c;
    }
    init_mid();

    ull ret = F(i + 2, 0);
    if (n == i)
    {
        return cached[i];
    }
    else if (n == i + 1)
    {
        return cached[i + 1];
    }
    else
    {
        return ret;
    }
}

int main()
{
   // freopen("1input.txt", "r", stdin);
    ios_base::sync_with_stdio(0);

    cout.tie(0);
    cin.tie(0);

    int i = 1;
    while (cin >> n >> p)
    {
        if (n < 0)
            break;

        memset(cached, 0, sizeof(cached));

        std::cout << "Case " << i++ << ": ";
        std::cout << solve() << "\n";
    }
    return 0;
}
// left mid mid

void failure(const string &B, vector<long long> &fail)
{
    size_t n = B.size();
    fail.resize(n);
    fail[0] = -1;
    for (int start = 1; start < n; start++)
    {
        int before = fail[start - 1];
        while (B[before + 1] != B[start] && (before >= 0))
            before = fail[before];
        if (B[before + 1] == B[start])
            fail[start] = before + 1;
        else
            fail[start] = -1;
    }
}

ull kmpSearch(const string &A, const string &B, vector<long long> &fail)
{
    ull count = 0;
    long long i = 0, j = -1;
    long long n = A.size(), m = B.size();
    while (i < n)
    {
        if (A[i] == B[j + 1])
        {
            if (j + 1 == m - 1)
            {
                j = fail[j + 1];
                count++;
            }
            else
            {
                j++;
            }
            i++;
        }
        else
        {
            if (j == -1)
            {
                i++;
            }
            else
            {
                j = fail[j];
            }
        }
    }
    return count;
}