백준 5904번 Moo게임

www.acmicpc.net/problem/5904

 

 

 

 

<접근방법>

어림수로 k의 최댓값은 30이하이다.

 

3개의 조각( s(k-1), 'moooo...', s(k-1)) 중 하나를 타고 들어간다.

3번째 조각을 타고 들어갈 때, n의 인덱스를 s(k-1)에 맞게 갱신해주어야 한다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
using  namespace  std;

long long n;
long long Size[31];

char S(int k) {
	if(k == 0){
		if (n == 0) return 'm';
		else return 'o';
	}

	if (n < Size[k - 1]) {
		return S(k - 1);
	}
	else  if (Size[k-1] <= n && n <  (Size[k-1] + k + 3)) {
		if (n == Size[k - 1]) return 'm';
		else return 'o';
	}
	else {
		n -= (Size[k - 1] + k + 3);
		return S(k-1);
	}
}

long long retSize(int k) {
	if (k == 0) {
		return Size[k] = 3;
	}
	return Size[k] = retSize(k - 1) * 2 + k + 3;
}

int main() {
	cin >> n;
	n--;
	retSize(30);
	cout << S(30) << '\n';
	return 0;
}