백준 11585 속타는 저녁 메뉴 (c++) : 피너클

11585번: 속타는 저녁 메뉴

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

 

kmp와 gcd를 이용해서 풀었다.

 

I W A N T M E A T
E A T I W A N T M

위에가 고기를 먹을 수 있는 원판의 모양고 아래가 현재의 원판이다.

원판을 계속 회전하면서 하나하나 맞춰야 할것 같지만

I W A N T M E A T
E A T I W A N T M E A T I W A N T M

이렇게 아래 있는 현재의 원판을 한번 더 적고 비교하면 된다.

I W A N T M E A T
E A T I W A N T M E A T I W A N T M

  I W A N T M E A T
E A T I W A N T M E A T I W A N T M

	I W A N T M E A T
E A T I W A N T M E A T I W A N T M

	  I W A N T M E A T
E A T I W A N T M E A T I W A N T M

		I W A N T M E A T
E A T I W A N T M E A T I W A N T M

이런 식으로

 

int n;
char a[1000001], b[2 * 1000001];
int f[2 * 1000001];

사용할 변수들이다. a와 b에 원판들을 담는다. b는 두배로 들어가니 *2를 해줬다.

f는 kmp에 사용할것이다.

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

gcd함수다.

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		b[n + i] = b[i];
	}

입력받을때 b에는 추가로 더 넣어준다.

a[0] = '#';
b[0] = '#';

f[0] = -1;
for (int i = 1; i <= n; i++) {
	int j = f[i - 1];
	while (j >= 0 && a[j + 1] != a[i]) j = f[j];
	f[i] = j + 1;
}

그 뒤로는 kmp준비해주고

	int j = 0;
	int ans = 0;
	for (int i = 1; i <= 2 * n -1; i++) {
		while (j >= 0 && a[j + 1] != b[i]) j = f[j];
		j++;
		if (j == n) {
			ans++;
			j = f[j];
		}
	}

돌려주면 끝난다. 이때 2 * n - 1까지 확인해줘야 한다.

2 * n까지 확인하면 같은 원판이 두번 들어가게 된다.

	if (ans == n) {
		cout << "1/1" << '\n';
		return 0;
	}

	int m = gcd(ans, n);
	//cout << ans << ' ' << m << '\n';
	cout << ans / m << '/' << n / m << '\n';

	return 0;
}

그 후 ans와 n이 같으면 1/1을 출력하고 

아니면 gcd를 이용해서 기약분수로 출력한다.

 

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

using namespace std;

int n;
char a[1000001], b[2 * 1000001];
int f[2 * 1000001];

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

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		b[n + i] = b[i];
	}

	a[0] = '#';
	b[0] = '#';

	f[0] = -1;
	for (int i = 1; i <= n; i++) {
		int j = f[i - 1];
		while (j >= 0 && a[j + 1] != a[i]) j = f[j];
		f[i] = j + 1;
	}

	int j = 0;
	int ans = 0;
	for (int i = 1; i <= 2 * n -1; i++) {
		while (j >= 0 && a[j + 1] != b[i]) j = f[j];
		j++;
		if (j == n) {
			ans++;
			j = f[j];
		}
	}

	if (ans == n) {
		cout << "1/1" << '\n';
		return 0;
	}

	int m = gcd(ans, n);
	cout << ans / m << '/' << n / m << '\n';

	return 0;
}

전체코드다.