[PS] 백준 11585번: 속타는 저녁 메뉴

|

문제

내가 이해한 문제 내용

KMP를 활용하는 문제로 룰렛(원형)으로 주어지기 때문에 생각을 좀 더 해야되는 문제이다. 고기를 먹을 수 있는 룰렛형태가 주어지고 현재 룰렛 형태가 주어질 때 현재 룰렛 형태를 기준으로 몇 번 고기를 먹을 수 있는지를 묻는 것이다.

접근 방식

예제에선 AABAAB가 고기 문자열이고 BAABAA가 현재 문자열인데 문제의 조건이 적어도 1번은 매칭된다고 했기 때문에 단순히 고기 문자열에서 마지막 실패 함수값을 활용했다.

어려웠던 점 & 배운 점

근데 기존 풀이는 룰렛을 전부 조사하기 위해서 고기 문자열을 2개 이어붙인다음 현재 문자열로 KMP를 돌리는 방식이었다. 원형 문자열을 검사할 때 이렇게도 쓸 수 있구나 하는 것을 배웠다.

코드

#include <cstdio>
#include <vector>
using namespace std;

vector<int> f,r;
vector<char> roul1,roul2;

int failure_function(const vector<char>& s)
{
    int n = s.size();
    f.resize(n);
    int begin=1, m=0;

    while(begin < n){
        if(s[begin+m]==s[m]){
            m++;
            f[begin+m-1] = m;
        } else{
            if(m==0) begin++;
            else{
                begin += (m-f[m-1]);
                m = f[m-1];
            }
        }
    }
    return n/(n-f[n-1]);
}

int gcd(int a, int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

int main(void)
{
    int a;
    scanf("%d",&a);
    roul1.resize(a);
    roul2.resize(a);
    for(int i=0; i<a; i++) scanf(" %c",&roul1[i]);
    for(int i=0; i<a; i++) scanf(" %c",&roul2[i]);

    int b = failure_function(roul1);
    int g = gcd(a,b);
    printf("%d/%d",b/g,a/g);
    return 0;
}