[C++]백준 - 1305번 문제

1305번: 광고 (acmicpc.net)

1305번: 광고

 

1305번 : 광고

---

세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.

전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.

광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.

예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.

세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다.

• 1 ≤ L ≤ 1,000,000
• 광고판에 보이는 문자열은 알파벳 소문자로만 이루어져 있다.

출력

---

첫째 줄에 가능한 광고의 길이중 가장 짧은 것의 길이를 출력한다.

 

---

 

생각해 볼 점

---

KMP 알고리즘에서 실패함수를 이용하는 문제입니다.

 

4354번 문제와 유사한 풀이법 : 

 

예시) ABCAB의 실패함수

Index	0	1	2	3	4
Pi[index]	0	0	0	1	2

위 표와 같이 생성이 되었을 것입니다. 여기서

 

Pi의 마지막 원소를 보면 Pi[L - 1] == 2 입니다.

 

마지막 두 글자는 첫 두 글자 "AB"를 반복하고 있다는 뜻입니다.

 

즉, ABCAB에서 AB는 반복되고 있으므로 답은 AB를 제거한 ABC가 될 것입니다.

 

답은 L - Pi[L - 1]을 제출합니다.

 

코드

---

#include <iostream>
using namespace std;


int main()
{
	int L;
	cin >> L;
	char *input = new char[L + 1];
	cin >> input;

	int* Pi = new int[L];
	fill_n(Pi, L, 0);

	//실패함수
	for (int left = 0, right = 1; right < L; right++)
	{
		while (0 < left && input[left] != input[right]) left = Pi[left - 1];
		if (input[left] == input[right]) Pi[right] = ++left;
	}

	cout << L - Pi[L - 1];

	delete[] Pi;
	delete[] input;
	return 0;
}

 

그 외

---