[백준 / BOJ] 1305 광고

문제

출처 : https://www.acmicpc.net/problem/1305

1305번: 광고

세준이는 길 한가운데에서 전광판을 보고있다. 전광판에는 광고가 나오고있다.

전광판의 크기는 전광판에서 한번에 보이는 문자열의 최대 길이를 나타낸다.

 

전광판의 크기 L과 세준이가 본 전광판의 글자가 주어졌을때, 가능한 광고길이중 최솟값을 출력하는 문제다.

 

풀이

모든경우를 보면, L^2이 되서 시간안에 통과하지못한다.

 

KMP알고리즘을 이용해 푼문제다.

 

광고판에서 광고가 나올수있는 경우는 광고 A뒤에 똑같은 광고 A가 이어서 나오는 경우밖에없다(같은내용의 광고만 나온다 했으므로..). 즉, 광고 A의 접두사와 뒤에 나오는 광고 A의 접두사가 같은지 확인하면된다. 이는 KMP알고리즘의 희소배열을 만드는과정을 이용해 빠르게 알아낼수있다.

 

세준이가 본 전광판의 내용을 입력받고, 해당 문자열을 기준으로 희소배열을 생성한다. 이때, 희소배열 중간값은 중요하지않고, 끝값만 알고있으면된다. 전광판은 항상 똑같은 내용의 광고를 내보내므로, 희소배열의 마지막값이 0이라면, 중복되는 값이 없다는뜻이고, 중복 되는값이 없다면 아직 전광판의 광고가 안끝난것이기 때문이다.

 

이해가 안된다면, 다음과 같은 경우에서 광고의 최소길이를 구해보도록 하자.

 

9

abcabcdef

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1305%20%EA%B4%91%EA%B3%A0/main.cpp

devxb/JJUNalgo