[백준] divide and conquer)5904 Moo 게임

 

문제

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

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 m o o o o o 

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "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 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 109)이 주어진다.

출력

N번째 글자를 출력한다.

 

 

 

Moo수열의 N번째 글자를 구하기 위해서는 우선 N번째 글자는 S(k)와 S(k-1)에 존재할것이기 때문에 k를 먼저 찾고 시작합니다.

 

그리고 풀이 논리는 다음과 같습니다.

 

 

3 S(0)

3+4+3=10 S(1)

10+5+10=25 S(2)

25+6+25=56 S(3)

ex)50 >> S(3)에서 50번재 알파벳을 구하세요 문제를 쪼갤 수 있다

56-25-6 = 25
50-25-6 = 19

ex)19 >> S(2)에서 19번째 알파베슬 구하세요

25-10-4 =11
19-10-4=5

ex)S(1)에서 5번째 알파벳을 구하세요

10-3-4=3

 

S(0)에서 2번째 알파벳을 구하세요
5-3=2 >> moo에서 2번째 글자를 찾으세요 = 2

 

문제를 쪼갤 수 있다는게 핵심입니다.

divide and conquer 문제입니다.

 

S(K)에서 n번째 알파벳이

1. 첫번째 S(k-1)에 존재하는지

2. 두번째 Mooo... 에 존재하는지 >> 이경우 답을 출력합니다

3. 세번째 S(k-1)에 존재하는지

 

4.위를 반복해서 K=0이되면 탈출합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int n;
ll s[31];
int main() {
	FAST;
	cin >> n;
	int k = 1;
	s[0] = 3;
	while (s[k-1]<n) {
		s[k++] = 2 * s[k - 1] + 3 + k;
	}
	int idx = k - 1;
	int mid = k + 2;
	while (1) {
		if (idx == 0)break;
		else if (n <= s[idx - 1]) {
			idx--;
			mid--;
		}
		else if (n - s[idx - 1] <= mid) {
			if (n - s[idx - 1] == 1) {
				cout << 'm';
				return 0;
			}
			cout << 'o';
			return 0;
		}
		else {
			n = n - s[idx - 1] - mid;
			idx--;
			mid--;
		}
	}
	n == 1 ? cout << 'm' : cout << 'o';
}