[2017-10-10] Secret Cow Code

링크 : https://www.acmicpc.net/problem/14454

어떤 문자열 S에 대해 그 문자열을 오른쪽으로 한 칸 민 문자열을 원래 문자열 S 뒤에 덧붙여 2배로 긴 새로운 문자열로 만드는 연산을 F라고 하자. 첫 문자열 S가 주어지고 여기에 F를 무한 반복해서 나오는 어떤 문자열이 있다고 했을 때, 그 문자열에서 n번째 위치에 어떤 문자가 들어갈 지를 구하는 문제다.

 얼핏 생각하면 좀 까다로울 수 있는데, n번째 위치를 크게 나눠서 생각하면, 원래 문자열 s에 F를 쭉 반복해서 붙인 문자열 중 길이가 n보다 작으면서 가장 긴 걸 K라고 하자. 그러면 n번째 위치는 K를 오른쪽으로 한칸 민 문자열에서 n - (K의 길이) 위치에 있는 문자가 된다. 그러면 여기서 거꾸로 돌아가 n번째 위치의 문자가 문자열 K에서 어느 위치에 있는 문자인지 알 수 있다. 그러면 이제 다시 이 새로운 N에 대해서 동일한 동작을 반복하고, 쭉 반복하다가 N이 처음 문자열의 길이보다 작아지면 그 때 그 위치에 있는 문자를 출력하면 된다. 시간 복잡도는 효율적으로 잘 짜면 O(logn)인데, 귀찮아서 O(log^2n)으로 풀었다. n 범위상 어차피 시간 안에 나온다.