[BOJ 11590] COCI 2015/2016 #2 SAVEZ

https://www.acmicpc.net/source/share/412dd80e9e794587a5a0f3b851164ff7

공유 소스 보기

 

KMP로 모든 string마다 suffix와 prefix가 같은 suffix/prefix의 길이를 찾을 수 있다는 생각을 했는데, 답을 빠르게 찾는데는 큰 도움이 되지 않았다. 생각이 안나서 결국에 공식풀이를 봤는데, 매우 신기한 방법이 있었다.

 

이 문제에서 a가 b와 이어질려면 a가 b의 prefix이면서 suffix이여야 한다. 이 때 suffix 조건을 제거해보자. prefix만 본다면 이 문제는 trie로 어렵지 않게 풀 수 있다. 각 노드마다 (이 노드에서 끝나는 string이 있다면)이 노드의 string에서 끝나는 최적의 답을 저장하면, 새로운 string에 대해 trie를 빌드할 때 지나가는 노드들 ≡ 새로운 string의 앞에 놓을 수 있는 string이니까 지나가면서 가장 큰최적값을 취해서 +1한 값을 새로 만든 string의 leaf에 놓으면 된다.

이제 다시 suffix조건을 가져오자. 어떻게 prefix만 보면서 suffix도 확인할 수 있을까? 잠시 생각해보면, a가 b의 suffix라는 것은 a를 뒤집었을 때 b를 뒤집은 것의 prefix이라는 뜻이다. 일단 문제에서 suffix라는 단어를 없앴다! 그러면 이제 trie에 대해 쿼리를 할 때, 원래의 string과 뒤집은 string을 동시에 보면 된다. 구체적인 방법은, "abcde"라는 문자열이 있으면 이를 뒤집은 문자열과 합쳐서 "(a,e)(b,d)(c,c)(d,b)(e,a)"라는 , 한 글자 안에 두 개의 character가 있는 문자열로 생각하고 트라이로 보면 된다. 즉, 한 글자에 26*26개의 가능한 값이 생기는 것이다. 이렇게 하면 prefix가 겹치는 걸 확인하면 실제로는 같은 길이의 suffix도 같이 겹치는 것을 확인해볼 수 있다. 이제 맨 처음에 설명한 dp를 하면 된다.

구현 주의사항:
- 나이브한 트라이를 짜면 메모리 초과가 난다. 트라이의 노드에 하위 노드가 있는 child만 저장하도록 vector나 map을 쓰자.

 

---

혼자서 연습할 때는 너무 생각이 휙휙 지나갔는데, 내 생각을 남이 납득할 수 있을만큼 풀어서 쓰는 건 연습의 효율이나, 안정적인 마음가짐에 도움이 되는 것 같다. 병특을 핑계로 거의 만 1년동안 블로그에서 손을 뗐는데, PS를 계속 하는동안은 다시 좀 써볼려고 한다.