이번 연습에서 가장 재밌어보이는 문제 7번입니다.
요약: 주어진 N개의 a, t, g, c로만 이루어진 문자열을 accept시키는 regular expression 중 최소 길이인 것을 구하여라. (길이 합 최대 2천)
regular expression은 다음과 같이 정의됩니다. (평소에 사용되는 것의 정의와 비슷하지만, 다릅니다. 이해가 안되는 부분은 질문이나 검색을 통해 해결하세요.)
(1) "a", "t", "g", "c" 각각은 regular expression입니다. 이것들은 자기 자신만을 accept시킵니다.
(2) A, B가 모두 regular expression이라면, (AB) 또한 regular expression입니다. 이것은 A가 accept시키는 문자열과 B가 accept시키는 문자열을 하나씩 골라 이어붙인 것을 accept시킵니다.
(3) A, B가 모두 regular expression이라면, (A|B) 또한 regular expression입니다. 이것은 A가 accept시키는 문자열과 B가 accept시키는 문자열을 accept시킵니다.
(4) A가 모두 regular expression이라면, (A*) 또한 regular expression입니다. 이것은 A가 accept시키는 문자열을 0번 이상 이어붙인 것을 accept시킵니다. (꼭 같은 문자열을 이어 붙일 필요는 없습니다)
중요한 것은, 괄호가 필수입니다.
입력
2
a
gtc
출력
(a|(g(tc)))
입력
3
g
gg
ggg
출력
(g*)
구해야 되는 것은 M!가지 경우에 대한 모든 substring의 총합입니다.
정상적인 방법으로는 해결이 힘들기도 하고, 더블카운팅으로 문제를 바꾸면 쉬워지는 것 같아 보입니다.
substring은 하나의 시작 원소와, 하나의 끝 원소로 이루어져 있습니다. 임의의 수 2개를 정한 뒤, 하나를 시작으로, 나머지 하나를 끝으로 하는 구간들의 (M!가지의 배치에 대해) gcd 총합을 구해보기로 합니다.
> 이것을 구할 수 있다면, 더블카운팅 기법으로 다항시간 내에 답을 구할 수 있습니다.
모든 쌍에 대해 계산하는 것은 M^2으로 시간이 꽤 걸리기 때문에, 수의 크기가 작은 것을 이용해보기로 합니다.
gcd를 정한 뒤, substring의 gcd가 그 값인 것들의 개수를 세어보기로 합니다.
G라고 정합시다. 그러면, substring의 gcd가 G로 나누어 떨어지는 것들의 개수를 세면 됩니다.
> 이것이 되면, 포함과 배제로 문제를 해결할 수 있습니다.
gcd는 구간의 시작 원소, 끝 원소와, 사이에 끼어들어올 수 있는 구간의 개수 3개에 영향을 받습니다. 각각을 잘 계산한 뒤, 수식으로 잘 계산하면 해결 가능합니다.
조심하지 않으면 8만^2이 되기 때문에 알고리즘 설계를 조심할 필요가 있습니다.
풀이는 도토리가 완성하고 구현하였기 때문에 세부 내용은 잘 모릅니다.
