취미로 코딩하기

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

이번에 볼 문제는 백준 10977번 문제인 음식 조합 세기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10977

이 문제에서는 레스토랑의 메뉴들이 매일매일 다음 숫자의 메뉴로 바뀔 때 이 메뉴들의 주기를 구하는 문제이다.

즉, 이 문제는 다음과 같은 문제로 바꿔 생각할 수 있다:

첫 index가 1인, 0과 1로 이루어진 문자열에서 가장 짧은 반복주기를 계산한다. (단, 0은 해당 메뉴가 오늘 나오지 않았을 때, 1은 해당 메뉴가 오늘 나왔을 때에 대응된다)

이는 KMP 알고리즘을 구성할 때 사용하는 pi 배열을 이용하여 쉽게 계산할 수 있다.

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

#include <iostream>
#include <cstring>
using namespace std;

int food[1000000];
int pi[1000000];

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

    int T; cin >> T;
    while (T--) {
        memset(food, 0, sizeof(food));
        memset(pi, 0, sizeof(pi));
        int M, N; cin >> M >> N;

        while (N--) {
            int x; cin >> x;
            food[x - 1] = 1;
        }

        for (int i = 0; i < M; i++) {
            int idx = i;
            while (idx > 0) {
                if (food[pi[idx - 1]] == food[i]) break;
                idx = pi[idx - 1];
            }
            if (idx <= 0) pi[i] = 0;
            else pi[i] = pi[idx - 1] + 1;
        }
        int temp = M - pi[M - 1];
        if (M % temp == 0) cout << temp << '\n';
        else cout << M << '\n';
    }
}