[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 범위상 어차피 시간 안에 나온다.

	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <stdio.h>
	#include <map>
	#include <memory.h>
	#include <iostream>
	#include <string>
	#include <set>
	#include <math.h>
	using namespace std;
	using ii = pair<int, int>;
	using i64 = long long int;
	using ii64 = pair<i64, i64>;
	int main()
	{
	string code;
	i64 n;
	cin >> code >> n;
	n--;
	i64 len = code.size();
	while (n >= len)
	{
	i64 small = len;
	while (small * 2 <= n)
	{
	small *= 2;
	}
	n -= small;
	n = (n + small - 1) % small;
	}
	printf("%c", code[n]);
	return 0;
	}

view raw 14454.cpp hosted with ❤ by GitHub