[백준] 1305번 광고

문제: 1305번: 광고

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 어느 순간 전광판을 쳐다봤을 때, 가능한 광고의 길이 중 가장 짧은 것을 출력하는 문제
	// 즉, 전광판을 통해 생각해볼 수 있는 광고 문구 중에서 길이가 가장 짧은 걸 출력하면 됨.
	// 만약 현재 전광판의 문구가 aababba 이런 식이라고 했을 때, 가능한 가장 짧은 광고 문구는 어떻게 될까?
	// 일단 pi 배열을 이용하는 문제이다
	// a 일 땐 0, aa 일 땐 1, aab 일 땐 0, aaba 일 땐 1, aabab 일 땐 0, aababb 일 땐 0, aababba 일 땐 1
	// 이때 가능한 가장 짧은 광고 문구는 pi 의 맨 마지막 요소를 전광판의 크기에 빼주면 구할 수 있다.
	
	// 어떻게 이 풀이가 가능한가?
	// 문제 조건에서는 전광판을 다음과 같이 설명하고 있다. 
	// 전광판에는 광고가 흘러나오고 있다. 전광판에는 같은 내용의 문구가 무한히 반복되어 나온다.
	// 만약 광고하고 싶은 내용이 aaba 이고, 전광판 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa
	// 왜? 광고문구는 무한히 이어져 있는데 6칸만 보여지므로
	// 즉, 현재 광고판을 봤을 때 aabaaa 에서 2를 빼면 aaba 를 구할 수 있음
	// 그렇다면 이 2라는 값은 어떻게 구하는가? 위에서 설명한 방식으로 구할 수 있음
	// a:0, aa:1, aab:0, aaba:1, aabaa:2, aabaaa:2
	// 즉, 6에 aabaaa 경우의 suffix 값을 빼주면 되는 것.

	int l; // 전광판 길이
	cin >> l;
	string advertisement;
	cin >> advertisement;

	int m = advertisement.size();
	vector<int> pi(m + 1);

	int i = 1;
	int j = 0;
	while (i < m) {
		if (advertisement[i] == advertisement[j]) {
			i++;
			j++;
			pi[i] = j;
		}
		else if (j == 0) {
			i++;
			pi[i] = 0;
		}
		else {
			j = pi[j];
		}
	}
	cout << l - pi[m];


	return 0;
}

 

진짜 KMP 문제라는 걸 알고 시작했는데도 불구하고 풀이 방법이 전혀 떠오르지 않았다. 애초에 문제가 이해가 되지 않았었다.

 

문제가 말하고 있는 바는, 현재 전광판에 나타난 문구를 보았을 때 이로부터 가능한 광고 문구 중 가장 짧은 문구의 길이를 출력하는 것이었다.

 

나는 처음에 전광판의 특징을 설명하는 부분에 꽂혀서 아 이건 알겠는데 이제 어떡하라고 라고 생각을 했는데, 전광판의 특성을 알았으니까 이제 전광판을 보고 광고 문구를 유추하는 문제였던 것이었다....

 

이 문제는 pi 배열의 값만 찾을 줄 알면 바로 풀리는 문제였다. 구현하는 건 정말 쉬운데 규칙을 찾아내는 것이  진!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!짜 어려운 부분인 것 같고, 이 문제의 난이도를 납득시키는 부분인 것 같다....

 

골드도 어려운데 플래티넘 문제 풀려고 하니까 어지럽다. 머리 딸려서 풀이 방법도 모르겠고 정말 가지가지 한다.... 하지만 골드 문제 처음 풀었을 때도 어질어질 했었는데 지금은 어느정도 괜찮으니까 얘도 계속 풀다보면 괜찮아지지 않을까... 앞으로도 열심히 해야겠다........ ㅠ_ㅠ  

 

 

 

참고자료:

[백준 1305] 광고 C++ — 개발냥발    

[백준 1305] 광고 C++