[BOJ 8104 // C++] Fibonacci Words

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

 

이번에 볼 문제는 백준 8104번 문제인 Fibonacci Words이다.
문제는 아래 링크를 확인하자.

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

 

두 문자열 A와 B에 대하여 A+B에 문자열 S가 포함된 횟수는 (A에 포함된 S의 수) + (B에 포함된 S의 수) + (A와 B에 걸친 S의 수)와 같다는 점을 관찰하자.

 

이 점을 점화관계로 이용하면 앞 두 단계에 포함된 문자열의 수를 계속 관리해나가고 사이에 걸친 문자열의 개수를 계속 세나가는 것으로 문제를 해결할 수 있다.

 

한편, 문자열의 길이는 한 단계 지날 때마다 기하급수적으로 증가하므로 이를 직접 저장하면 저장해야하는 문자열의 길이가 매우 길어질 것이다. 우리는 다음 단계의 문자열을 구할 때 각각의 문자열의 앞과 뒤의, S의 길이(보다 하나 적은)만큼만의 부분문자열만 알아도 충분하므로 이 점을 이용해 저장할 문자열의 길이를 적절하게 관리해나가자.

 

위 관찰을 더 파고들면 더 많은 최적화 또한 가능하지만 이 문제의 해결에는 필요하지 않다. 관심이 있다면 더 생각해보자.

 

문제의 답이 64비트 정수 자료형의 범위를 넘을 수 있다는 점에 유의하자. 감이 잘 안 온다면, 찾아야 하는 문자열이 "a"로 주어지면 답이 피보나치 수와 같이 증가함을 관찰하고, 200번째 피보나치 수가 얼마나 큰지 확인해보자. 한편, 수가 매우 커지지는 않으므로 큰 수의 연산을 효율적으로 구현할 필요는 없다.

 

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

#include <iostream>
using namespace std;

int N;
string S;
string s[200], dp[200];

void calc(int idx, int val) {
    string A = dp[idx - 2], B = dp[idx - 1];
    while (A.length() < B.length()) A = "0" + A;
    while (A.length() > B.length()) B = "0" + B;
    bool carry = 0;
    int len = A.length();
    for (int i = len - 1; i > -1; i--) {
        int a = A[i] - '0', b = B[i] - '0';
        int x = a + b;
        if (carry) carry = 0, x++;
        if (x > 9) x -= 10, carry = 1;
        A[i] = '0' + x;
    }
    if (carry) A = "1" + A;
    B = to_string(val);
    while (A.length() < B.length()) A = "0" + A;
    while (A.length() > B.length()) B = "0" + B;
    carry = 0;
    len = A.length();
    for (int i = len - 1; i > -1; i--) {
        int a = A[i] - '0', b = B[i] - '0';
        int x = a + b;
        if (carry) carry = 0, x++;
        if (x > 9) x -= 10, carry = 1;
        A[i] = '0' + x;
    }
    if (carry) A = "1" + A;
    dp[idx] = A;
}

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

    cin >> S >> N;
    s[0] = "b", s[1] = "a";
    if (S == "a") dp[1] = "1";
    else dp[1] = "0";
    if (S == "b") dp[0] = "1";
    else dp[0] = "0";
    for (int i = 2; i < N; i++) {
        string tmp = "";
        if (s[i - 1].length() >= S.length() - 1) tmp += s[i - 1].substr(s[i - 1].length() - (S.length() - 1), S.length() - 1);
        else tmp += s[i - 1];
        if (s[i - 2].length() >= S.length() - 1) tmp += s[i - 2].substr(0, S.length() - 1);
        else tmp += s[i - 2];
        int tlen = tmp.length(), cnt = 0;
        for (int k = 0; k + S.length() <= tlen; k++) {
            if (tmp.substr(k, S.length()) == S) cnt++;
        }
        calc(i, cnt);
        s[i] = s[i - 1] + s[i - 2];
        if (s[i].length() >= S.length()) s[i] = s[i].substr(0, S.length()) + s[i].substr(s[i].length() - S.length(), S.length());
    }

    cout << dp[N - 1];
}