[BOJ] 5904 Moo게임 - JAVA

1. 문제

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번째 글자를 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  길이로 몇 번째 수열인지 알아낸다.

2.  전체 길이, 가운데 길이(root)를 이용해서 앞부분 길이를 알아낸다.

3.  만약 앞부분에 속한다면(front<=N) 가운데 길이를 1 줄이고 전체길이를 앞부분길이로 바꿔서 재귀호출한다.

4.  뒷부분에 속한다면(front+root>N) N에서 front+root를 뺀 후 moo(front,root-1)을 호출한다.

5.  가운데 부분에 속한다면 N에 front를 빼고 끝낸다.

6.  함수가 끝난 후 N값이 1이라면 m, 그 나머지는 o를 출력한다.

import java.io.*;

public class BOJ_5904_Moo게임 {
   static int N;
   public static void main(String[] args) throws IOException {
      N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

      //몇번째 수열인지 알아내기
      int len = 3;
      int root = 3;
      while(N>len){
         len = len*2+(++root);
      }

      //함수호출
      moo(len,root);

      //결과
      if(N==1) System.out.println('m');
      else System.out.println('o');

   }
   public static void moo(int len, int root){
      //앞부분 길이
      int front = (len-root)/2;

      if(front>=N){//N이 앞부분에 속한다면
         moo(front,root-1);
      }
      else if(front+root<N){//N이 뒷부분에 속한다면
         N-=(front+root);
         moo(front,root-1);
      }else{//N이 중간부분에 속한다면
         N-=front;
      }
   }
}

 

---

3. 결과