[BOJ/JAVA] 5904번: Moo 게임

5904번: Moo 게임

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

키워드

• S(0)을 길이가 3인 수열 "m o o”

• 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.

---

구현

• 정리하면 S(k) = S(k-1) + “m” + “o”*(k+2) + S(k-1) 이다.

• dp 를 이용하여 적당한 크기의 S(k)까지 각 수열의 길이를 저장하자.

dp(int n)

1. n == 0 인 경우
   • moo 이므로 3을 반환

2. moo[n] ≠ -1 인 경우
   • moo[n] 반환

3. moo[n] 계산
   • moo[n] = dp(n - 1) * 2 + (n + 2) + 1
   • moo[n] 반환

---

findMoo(int k, long left)

현재 S(k)이고, 앞에서 left번째 글자를 반환하는 메소드

1. k == 0 인 경우
   • moo 이므로
   • left == 1 이면 “m” 반환
   • 나머지는 “o” 반환

2. left < moo[k-1]+1 인 경우 (S(k-1) 안에서 처리 가능한 경우)
   • findMoo(k-1 ,left) 호출

3. left == moo[k-1]+1 인 경우 (S(k-1) 가 처리 되고 끝나는 경우)
   • “m” 반환

4. moo[k - 1] + 1 < left && left <= moo[k - 1] + k + 2 + 1 인 경우 (S(k-1) 처리 이후 다음 S(k-1)처리 전)
   • “o” 반환

5. 뒤 S(k-1)에 걸리는 경우
   • findMoo(k - 1, left - moo[k - 1] - k - 2 - 1) 호출

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class java_5904 {

    static int N;
    static long moo[];

    static long dp(int n) {
        if (n == 0) {
            return 3;
        }

        if (moo[n] != -1) {
            return moo[n];
        }

        moo[n] = dp(n - 1) * 2 + (n + 2)+1;

        return moo[n];
    }

    static char findMoo(int k, long left) {
        if (k == 0) {
            if (left == 1) {
                return 'm';
            } else {
                return 'o';
            }
        }

        if (left < moo[k - 1] + 1) {
            return findMoo(k - 1, left);
        }

        // 첫 S(k-1) 을 전부 포함하는 경우 -> k
        if (left == moo[k - 1] + 1) {
            return 'm';
        }

        // 사이에 있는 경우
        // o
        if (moo[k - 1] + 1 < left && left <= moo[k - 1] + k + 2 + 1) {
            return 'o';
        }

        // 뒤 S(k-1) 을 전부 포함하는 경우
        return findMoo(k - 1, left - moo[k - 1] - k - 2 - 1);
    }

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

        N = scanner.nextInt();

        moo = new long[25];

        Arrays.fill(moo, -1);

        moo[0] = 3;

        dp(24);

        char result = findMoo(24, N);

        System.out.println(result);

        scanner.close();
    }
}

---

Uploaded by N2T