[BOJ 14454] Secret Cow Code

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

14454번: Secret Cow Code

 

- 문제 요약

 

문자열 S(최대 30글자)와 N(N <=10^18)이 주어집니다.

문자열 S를 오른쪽으로 한 칸 밀어서 원래의 S의 뒤에 붙여 길이를 2배로 만드는 연산을 F(S)라고 합니다.

F(S)를 반복적으로 수행해서 문자열을 만들었을 때, N번째 위치에는 어떤 문자가 있는지 출력하세요.

 

 

- 알고리즘 정리

 

문제에서 주어진 테스트케이스인 COW 8을 이용해서 생각해보겠습니다.

COW에 F(S) 연산을 하면 COW => COWWCO => COWWCOOCOWWC와 같은 형태로 문자열이 만들어질 것입니다.

여기서 문자열의 길이로 문자열을 쪼개보면 아래와 같은 형태가 될 것입니다.

COW => COW / WCO => COWWCO / OCOWWC

 

COWWCOOCOWWC에서 N보다 작거나 같지만 가장 긴 문자열을 SS라고 가정하겠습니다.

SS는 COWWCOOCOWWC일 것이고, SS의 길이는 6입니다.

그러면 N의 위치는 (N-SS의 길이)가 됩니다.

이를 이용해서 반복문을 돌리다가 N이 S의 길이보다 작아지면 Break를 걸고 현 Index의 문자를 출력해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
string s;
ll n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s>>n;
	n--;
	while(n>=s.size()){
		ll mn=s.size();
		while(mn*2<=n){
			mn*=2;
		}
		n-=mn;
		n=(n+mn-1)%mn;
	}
	cout<<s[n];
}

코드 제출 결과