백준 5904

• 목차

  문제

  코드

  해설

문제

---

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 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다.

https://www.acmicpc.net/problem/5904

코드

---

• 코드 보기

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class Main {
  
      static int N;
      static int[] S;
  
      static boolean binarySearch(int offset, int index) {
          int mid = offset + S[index-1] + (index + 2);
          if(N <= offset + S[index-1]) {
              return binarySearch(offset,index-1);
          } else if(N <= mid) {
              return N == mid - (index + 1);
          } else {
              return binarySearch(mid, index-1);
          }
      }
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          S = new int[50];
          int index = 0;
          while(N>S[index]) {
              index++;
              S[index] = S[index-1] * 2 + (index + 2);
          }
          if(binarySearch(0,index)) System.out.println("m");
          else System.out.println("o");
      }
  
  }

해설

---

문제의 N의 범위가

1 ≤ N ≤ 10^9 이므로 O(N) 으로는 풀 수 없고

이분탐색을 이용하여 풀었다

• 1. 점화식을 통해 N번째 글자가 나오기 시작하는 S(k) 구하기

  • 코드

    S = new int[50];
    int index = 0;
    while(N>S[index]) {
        index++;
        S[index] = S[index-1] * 2 + (index + 2);
    }

  • 점화식

    S[index] = S[index-1] * 2 + (index + 2);

    문제에서는 S(k)를 수열 자체로 봤지만

    여기 코드에서는 수열의 길이로 두었다

    ( 수열 자체로 두면 10^9 길이의 문자열은 메모리 제한을 벗어난다 )

    문제에서

    

    이라고 하였고 k 대신 index를 쓴 것을 제외하고는 완벽히 똑같다는 걸 알 수 있다

    그리고

    `N번째 글자가 나오기 시작하는 S(k)` 를 구하기 위해

    수열의 길이가 N 보다 작은 동안은 점화식을 계속 반복했고

    N과 같거나 큰 순간 while 문을 빠져 나왔다

---

• 2. 이분탐색으로 통해 N번째 위치에 있는 글자 구하기

  • 코드

    static boolean binarySearch(int offset, int index) {
        int mid = offset + S[index-1] + (index + 2);
        if(N <= offset + S[index-1]) {
            return binarySearch(offset,index-1);
        } else if(N <= mid) {
            return N == mid - (index + 1);
        } else {
            return binarySearch(mid, index-1);
        }
    }

  앞서 N번째 글자가 나오기 시작하는 index를 구했고 그 index를 가지고

  binarySearch(0,index)

  위와 같이 main 함수에서 재귀함수를 호출했다

  재귀함수에는 이분탐색을 위해

  현재 탐색하고 있는 수열의 index와

  현재 탐색의 offset(시작위치)을 매개변수로 받고 있다

  💡

  이분탐색을 사용할 때 보통 재귀함수를 사용하여 구현하는 게 개인적으로 보기도 쉽고 구현도 잘된다

  수열의 구분

  문제에서 알 수 있듯이

  수열 규칙상

  

  수열을 앞부분, 중간부분, 뒷부분으로 구분 지을 수 있고

  여기서 핵심은

  중간부분은 index가 몇이 되든

  "mooo..." 와 같이 맨 처음만 m이고 나머지는 o라는 사실이다

  따라서,

  else if(N <= mid) {
      return N == mid - (index + 1);

  N이 맨 처음이면 return true → main함수에서 "m" 출력

  아니면 return false → main함수에서 → "o" 출력

  하여 N번째 글자를 출력했다

  💡

  그 외에 앞부분과 뒷부분은 S[index-1]의 길이이므로 index를 하나씩 줄여 다시 탐색하고 있고 - 앞부분은 offset을 그대로 - 뒷부분은 offset을 mid로 바꿔 N이 중간부분에 위치할 때까지 탐색을 하는 것을 볼 수 있다