[BOJ] 5904. Moo 게임

[작성일]

• 2022-03-13

[분류]

• 재귀
• 분할정복
• dp
  
  
  

[문제링크]

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

[요구사항]

• N번째 글자를 출력한다.
  
  
  

[풀이]

분할정복을 이용해서 푸는 문제이다.
1) 우선 S(k)의 길이를 미리 구해놓는다. N이 10^9 = 10억 < 2^30 이기 때문에 k는 최대 30까지 밖에 안되기 때문에 dp[30]까지 구한다.
2) 이제, moo 재귀함수를 이용해서 N번째 글자를 찾아낸다.

• n이 1일 경우 : m 출력
• n이 2, 3일 경우 : o 출력
• 그 외
  - 우선, n보다 dp[k]가 커지는 시점까지 while문으로 구한다. 이후, mid 값을 정한다.
  여기서 mid = 중간 m + ooo... 끝의 o 자리이다. 그 자리 보다 뒤에 있을 경우에는 n을 dp[k-1]에서 처리할 수 있도록 n자체를 mid 만큼 빼고 moo 함수를 다시 실행한다. n이 dp[k-1] + 1인 경우 무조건 m이므로 m을 출력하고 나머지의 경우에는 o를 출력한다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    static char answer;
    static int[] dp;

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

        // dp부터 n이상 범위까지 설정하기
        dp = new int[31];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 3;
        int i = 0;
        while (dp[i] <= N) {
            i++;
            dp[i] = dp[i - 1] + i + 3 + dp[i - 1];
        }

        moo(N);
        System.out.println(answer);
    }

    public static void moo(int n) {
        // moo로 위치 구하기
        int i = 31;

        if (n == 1) {
            answer = 'm';
        } else if (n <= 3) {
            answer = 'o';
        } else {
            while (dp[i - 1] >= n) i--;
            int mid = dp[i - 1] + i + 3;
            if (mid < n) moo(n - mid);
            else if (n == dp[i - 1] + 1) answer = 'm';
            else answer = 'o';
        }
    }
}