[JAVA]백준 5904번: Moo 게임

www.acmicpc.net/problem/5904

5904번: Moo 게임

 

1. 문제 설명

 

문자열 S(k)는 S(0)="moo", S(k)=S(k-1)+m+o가 k+2개+S(k-1)인 문자열이다.

 

N이 주어졌을 때, S(k)의 N번째 글자를 구하는 프로그램을 작성하는 문제이다.

 

N을 분할해 나가면서 문제를 해결하였다.

 

먼저 최초로 N보다 큰 문자열의 길이를 구한다.

 

구한 문자열이 S(X)라고 할 때, S(X)=S(X-1)+m+o가 X+2개+S(X-1)이다.

 

N보다 최초로 큰 문자열 이기에 N은 처음 등장하는 S(X-1) 문자열에 속할 가능성은 없다.

 

N이 존재할 경우는 3가지가 있다.

 

1. S(X-1)+m+o가 X+2개+S(X-1) 일 경우 => m 출력

2. S(X-1)+m+o가 X+2개+S(X-1)에 존재할 경우 => o 출력

3. S(X-1)+m+o가 X+2개+S(X-1)에 존재할 경우 => S(X-1) 문자열에서 N이 어디에 위치하는지 확인한다.

 

 

 

2. 코드

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static char answer;

    public static void main(String[] args) throws IOException {
        Scanner scan=new Scanner(System.in);

        int num=scan.nextInt();


        Moo(num);

        System.out.println(answer);

        scan.close();


    }

    public static void Moo(int num){
        int size=3;
        int index=0;

        if(num==1){
            answer='m';
        }else if(num<=3)
            answer='o';
        else{
            while(size<num){
                size=size*2+index+4;
                index++;
            }

            int front_back=(size-index-3)/2;



            if(size-front_back+1<=num){
                Moo(num-size+front_back);
            }else if(num==front_back+1)
                answer='m';
            else
                answer='o';
        }


    }




}