백준 11585 : 속타는 저녁 메뉴 (C++)

본문 링크

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int total=0; // 원하는 문자열이 나올 횟수를 저장할 전역변수 선언


vector<int> maketable(string pattern) // 테이블을 만드는 함수. 
{
    int patternsize = pattern.size();

    vector<int> table(patternsize , 0);

    int j = 0 ;

    for (int i = 1;  i < patternsize ; i++)
    {
        while( j > 0 && pattern[i]!=pattern[j])
        {
            j=table[j-1];
        }

        if (pattern[i]==pattern[j])
        {
            table[i]=++j;
        }
    }
    
    return table;
}

void KMP(string parent ,string pattern) // KMP 함수 , 두 문자열이 같은지 확인한다.
{
    int parentsize = parent.size();
    int patternsize= pattern.size();

    vector<int> table = maketable(pattern);

    int j = 0;

    for (int i = 0 ; i < parentsize ; i++)
    {
        while(j>0 && parent[i]!=pattern[j])
        {
            j=table[j-1];
        }

        if (parent[i]==pattern[j])
        {
            if (j==patternsize-1)
            {
                total++; // 만약 두 문자열이 같다면 횟수를 증가시켜준다.
                j=table[j];
            }
            else
            {
                j++;
            }
        }
    }

}

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

    int N;

    cin >> N;
    cin.ignore(); // 정수 입력받았으면 줄바꿈 문자 제거해야함.

    string parent2;
    string pattern;

    getline(cin , parent2);
    getline(cin , pattern);

    parent2.erase(remove(parent2.begin() , parent2.end(), ' ') , parent2.end()); // 공백 문자 제거
    pattern.erase(remove(pattern.begin() , pattern.end() , ' ') , pattern.end()); // 공백 문자 제거

    string parent; 

    parent += parent2;
    parent += parent2; // 기존의 문자열을 2배로 한다

    parent=parent.substr(0, parent.size()-1); // 그리고 마지막 값을 빼준다.

    KMP(parent , pattern);


    cout << "1/" << N/total; // 기약분수로 나타내기 위해서 1과 몫을 출력한다.

}

📌 어떻게 접근할 것인가?

KMP 를 사용해서 풀었습니다.
룰렛은 원형이기 때문에 기존의 문자열에서 2배를 해주고 마지막 뒤에 값 하나를 빼줍니다.

문제에서 원하는 바는 원형 룰렛을 돌렸을 때 오늘 저녁으로 고기를 선택하게 되는 확률 입니다.

• 6
  A A B A A B
  B A A B A A

위와 같은 룰렛이 있을때 현재 상태의 룰렛의 2배를 하고 마지막 값을 빼보겠습니다.
마지막 값을 뺴는 이유는 중복이 생길 수 있기 때문입니다.

• A A B A A B
• B A A B A A B A A B A

이때 B A A B A A B A A B A 에서 A A B A A B 는 총 2번이 나옵니다.

즉 확률적으로 2/6 이 되어서 결국 1/3 이 됩니다.

따라서 룰렛을 돌렸을때 원하는 문자열이 나올 확률을 구해주시면 됩니다.