BOJ 15507번: 연산 최적화

개요

- 알고리즘 분류: KMP, BFS

- 문제에 대한 평가: 아이디어가 기발함. 함수를 단순화해서 문제를 해결하는 것에 대한 시사점을 제공함.

 

문제 요약

0과 1로만 이루어진 길이 N의 문자열 S가 있다. 연산 F는 다음의 세 연산으로만 이루어진다.

A: 끝에 0 추가, B: 끝에 1 추가, C: 앞의 문자열을 한번 더 복사

A, B, C의 합성으로 이루어진 함수 F에 대해, F(F(O)) = S인 F가 존재하는지 판별하고, 존재한다면 이중 합성횟수가 가장 작은 것의 횟수를 구하라. 단, O는 빈 문자열이다.

 

문제 풀이 과정

문자열에 대해 여러 가지를 시도해 보았으나 잘 안 되었다. 그래서 가장 원초적인 것부터 하기로 했다. 문자열의 길이만 따지는 것이다.

길이가 X인 문자열에 A, B, C를 적용하면, 자명히 길이는 X+1, X+1, 2X가 된다. 결국 이들의 합성으로 이루어진 F는 문자열의 길이 X에 대해 X -> (2^e)X + b(e, b는 음 아닌 정수) 꼴이 된다.

따라서 F(F(O))의 길이는 (2^e)((2^e)*0 + b) + b = b(2^e + 1)이다. 이 식이 N이 되는 b와 e는 별로 없다(단적으로 e = 0, 1, ..., 19 만 대입해봐도 된다). 즉, b와 e가 고정된 상황에 대해서 문제를 해결하면 충분하다.

이제 여기까지 왔으면 문제가 매우 쉬워졌다. 왜냐하면 F(O)의 길이도 나왔기 때문에, 각 칸에 대해 C 적용이 되는지 여부를 저장해 놓으면, 결국 S[1...|F(O)|]와 S[|F(O)|+1...N] 각각에서 순서까지 똑같도록 A, B, C의 수열을 추출해내는 걸로 생각할 수 있기 때문이다. 이는 문자열이 어디에서 잘리는지 모르는 원래 문제보다 훨씬 쉽기 때문에 여기서부터 자신 있게 풀이를 생각하기 시작했다.

조금만 더 생각해 보니 위의 문제는 BFS로 해결됨을 알 수 있었다. 여기서도 똑같이 파라미터 e와 b를 사용하는데, 문자열이 결정 되었으므로 앞의 것은 b, 뒤의 것은 2^e * X + b 번째에 해당하는 것만 주어지면 충분하기 때문이다. X는 초기에 BFS가 호출된 b이다.

해당하는 문자에서 모두 C 적용이 가능하면, (e, b) -> (e-1, b/2)로 갈 수 있다. 물론 b는 짝수여야 한다.

해당하는 문자가 같으면, (e, b) -> (e, b-1)로 갈 수 있다.

여기에서 e와 b에 대해 거리 배열을 만들어 놓고, (0, 0)으로 가는 최소거리를 찾으면 된다. 이 BFS의 시간복잡도는 O(eb)이다.

마지막으로 C 적용여부를 구하는 전처리만 하면 되는데, 이는 매우 간단하다. KMP로 각각의 실패함수를 구한다. 우리는 실패함수를 따라 거슬러 올라간 것이 prefix=suffix인 모든 길이임을 알고 있으므로, 이것이 인덱스의 절반과 같은 경우가 있는지만 따지면 된다. 실패함수는 단사함수가 아니므로, 중복 체크를 피하기 위해서는 반대로 DFS식으로 내려가야 한다. 시간복잡도는 KMP와 C 적용가능성 전처리 모두 O(N)이다.

 

배운 점

함수가 복잡하면 함수의 인자의 일부 요소만 생각해서 특징을 파악한 뒤 확장한다(때로는 이것만으로 충분히 bruteforcing이 가능해질 수도 있다).

KMP에서 fail 함수를 거슬러 올라가 만나는 모든 값은 prefix = suffix인 모든 길이가 되며, 이를 반대로 fail 함수의 역을 저장한 후 내려간다고 생각하면 O(N)에 구할 수 있다.