알고리즘 문제
[C/C++ 백준 5904번] Moo 게임 (Silver 2)
새파란 공대생
2020. 9. 8. 19:22
5904번: Moo 게임
Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o
www.acmicpc.net
미리 해당 숫자가 무슨 Moo 수열에 들어가있을지 계산해주고, 분할 정복을 통해 점점 좁혀나가면서 범위를 줄여야한다.
#include <cstdio>
long long int Max[40];
void func(int cnt, int where){
if(cnt==3){
if(where==1)
printf("m");
else
printf("o");
}
else if(where<=Max[cnt-1]){
func(cnt-1, where);
}
else if(where>Max[cnt-1] && where<=Max[cnt-1]+cnt){
where -= Max[cnt-1];
if(where==1)
printf("m");
else
printf("o");
}
else{
where -= (Max[cnt-1]+cnt);
func(cnt-1, where);
}
}
int main(void){
int N, cnt=3;
scanf("%d", &N);
Max[3]=3;
for(int i=4; i<40; i++)
Max[i] = Max[i-1]*2+i;
while(N>Max[cnt]){
cnt++;
}
func(cnt, N);
}