[백준 5904] Moo 게임

문제 링크 : https://www.acmicpc.net/problem/5904

5904번: Moo 게임

 

예시를 먼저 보면 설명이 더 이해하기 쉬울 것이다.

 

m o o m o o o m o o m o o o o m o o m o o o m o o

 

재귀적으로 만들어진 세번째 moo 수열이다.

 

여기서 우리가 전체 문자열의 길이(s)와 중심 개인 문자열의 길이(k)를 알고 있다고 하자

 

위에서 그 값은 s=25, k=5

 

이 문자열에서 n번째 문자의 위치는 세가지 경우로 다룰 수 있다

 

1. 개인 문자열 k 안에 존재할 경우

 

2. 개인 문자열 k 보다 앞에 존재할 경우

 

3. 개인 문자열 k 보다 뒤에 존재할 경우

 

 

 

다음은 이를 n과 s,k를 사용하여 위 경우를 판별하는 조건식이다.

 

t = (s-k)/2 (t는 바로 전 문자열의 길이)

 

1. t < n <= t+k

2. t >= n

3. t+k < n

 

---

1번의 경우 바로 어떤 문자가 오는지 알아낼 수 있다.

 

그러나 2와 3의 경우는 다시 부분 문자열로 나눠서 살펴봐야 한다. 

 

이 경우 기존의 s는 t가 되고 k--가 될 것이다.

 

(t는 부분 문자열의 길이, 개인 문자열도 문자열을 한단계 낮춤으로 인해서 1만큼 짧아짐)

 

그리고 중요한 것은 s, k의 값을 수정함에 따라 n값이 수정되는 상황이 생길 수 있다는 것이다.

 

2번의 경우 그대로 놔둬도 상관 없지만, 3번의 경우 t+k만큼 앞의 문자열을 자르는 것이므로

 

n도 t+k만큼 감소해야 된다.

 

---

 

#include <iostream>
#define n_ 2200
using namespace std;

typedef long long ll;
ll n, k, s;

int main(void) {
	cin >> n;

	k = 4;
	s = 3;

	while (n > s) {
		s = s * 2 + k;
		k += 1;
	}

	k -= 1;
	while (1) {
		//cout << k << " " << s << " " << n << " " << endl;
		ll t = (s - k) / 2;
		if (n <= t) {
			k--;
			s = t;
		}
		else if (n > t + k) {
			n -= (t + k);
			k--;
			s = t;
		}
		else {
			n -= t;
			break;
		}
	}

	if (n == 1) {
		cout << 'm' << endl;
	}else{
		cout << 'o' << endl;
	}

	return 0;
}