[C++/9519] 졸려

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

졸린문제, 이 문제도 몇번의 눈 깜박임 후에 문자열이 바뀌는 문제입니다. 근데 그 눈 깜박임이 1,000,000,000번 까지 가능합니다. 그럼 100억을 다 할 수 있을까요? 절대 그럴 수 없습니다. 이런 문제는 Cycle이 존재하는지 확인하는 겁니다. 그렇다면 문제를 쉽게 해결할 수 있습니다. 그리고 문자열이 변경되는것은 어떤 규칙을 따르고 있는데, 옮겨지는 맨 마지막 index를 파악해야 문제를 쉽게 해결 할 수 있었습니다. 맨 마지막에서 부터 -= 2 씩 index를 옮겨가면서 규칙을 따를 수 있기 때문입니다. 맨 앞은 0부터 시작되기 때문에 상관이 없고, 맨 뒤는 index를 구해야합니다.

그렇다면 맨 뒤 index를 어떻게 구할 수 있을까?

1번에 위치한 문자를 제외한 몇개의 문자를 갖고 있고, 맨 뒤의 index는 무엇인지 파악해야한다. 그렇다면? 1번부터 2칸씩 이동하면서 맨 뒤의 index를 파악할 수 있다. 그렇다면 우리는 어떻게 구하냐?

문자열의 길이를 2로 나누게 된다. 홀수라면? 만약 7이라면 (4/3)으로 나뉘어지고, 6이라면? (3/3)으로 나뉘어진다. 그렇기 때문에 길이에서 2로 나누어준 후에 현재 위치를 제외해 그 값만큼 index를 1부터 이동시켜주면 된다.

그 후 lastIdx부터 -=2 만큼 이동하면서 새로운 문자열을 생성할 수 있다.

그 이후, 사이클을 제거하고 같은 방식으로 문제를 해결하면 된다.

아래는 정답 코드이다. 중복되는 코드가 존재하는데 이는 이후에 다시 정리할 예정이다.

#include<iostream>

using namespace std;

int n;
string original;

void init() {
	
	cin >> n >> original;
	
}

int sleeping() {
	
	int length = original.length();
	
	int backLen = (length / 2) - 1;
	int lastIdx = 1 + backLen * 2;
	
	int cnt = 0;
	string t = original;
	
	while(1) {
		cnt++;
		string temp = "";
		
		for(int i = 0; i < length; i+=2) {
			temp += t[i];
		}
		
		for(int i = lastIdx; i > 0; i-=2){
			temp += t[i];
		}
		
		t = temp;
		
		if(original == t) break;
	}
	
	return cnt;
}

void solve() {
	
	int circle = sleeping();
	
	int length = original.length();
	
	int backLen = (length / 2) - 1;
	int lastIdx = 1 + backLen * 2;
	n %= circle;
	
	string t = original;
	
	while(n--) {
		string temp = "";
		
		for(int i = 0; i < length; i+=2) {
			temp += t[i];
		}
		
		for(int i = lastIdx; i > 0; i-=2){
			temp += t[i];
		}
		
		t = temp;	
	}
	
	cout << t;
}

int main() {
	
	init();
	solve();
	
	return 0;
}