[Baekjoon] Moo 게임

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

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static String answer;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    static void sol() {
        String s0 = "moo";

        int mooLength = s0.length();
        int k = 0;

        while (mooLength <= N) {
            k++;
            mooLength = mooLength * 2 + getMiddleMooLength(k);
        }

        answer = dfs(k, mooLength);
    }

    static int getMiddleMooLength(int k) {
        return "m".length() + "o".length() * (k + 2);
    }

    static String dfs(int k, int mooLength) {
        if (k == 0) {
            if (N == 1) {
                return "m";
            } else {
                return "o";
            }
        }

        int previousMooLength = (mooLength - getMiddleMooLength(k)) / 2;

        if (isFrontMoo(previousMooLength)) {
            return dfs(k - 1, previousMooLength);
        }

        if (isMiddleMoo(k, previousMooLength)) {
            if (previousMooLength + 1 == N) {
                return "m";
            } else {
                return "o";
            }
        }
        if (isBackMoo(k, previousMooLength)) {
            N -= (previousMooLength + getMiddleMooLength(k));
            return dfs(k - 1, previousMooLength);
        }

        return "ERROR";
    }

    static boolean isMiddleMoo(int k, int previousMooLength) {
        return previousMooLength + 1 <= N && previousMooLength + getMiddleMooLength(k) > N;
    }

    static boolean isFrontMoo(int previousMooLength) {
        return N <= previousMooLength;
    }

    static boolean isBackMoo(int k, int previousMooLength) {
        return previousMooLength + getMiddleMooLength(k) <= N;
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }

    static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer);
        bw.close();
    }
}

주요 개념

• 분할 정복

풀이 방법

• 최대 입력 값이 10억인 만큼 단순 재귀로 풀면 메모리 초과가 발생한다.

• s0 -> A

• s1 -> A b A

• s2 -> AbA c AbA

• s3 -> AbAcAbA d AbAcAbA

• N의 위치가 Front 인지 Middle인지 Back 인지 판별하고 N이 포함하는 원래 형태의 Moo까지 내려가는 탑다운 방식이다.

  • AbAcAbAdAbAcAbA 에서 강조된 A의 위치가 N일 때, 다음과 같이 변한다.

  • isBackMoo() 트리거 -> AbAcAbA

  • isFrontMoo() 트리거 -> AbA

  • isBackMoo() 트리거 -> A("moo") -> N이 1이면 "m" 아니면 "o"

• N이 10억이어도 isBackMoo()가 트리거 되며 계속 N이 줄어들고 isMiddleMoo()에 트리거되지 않는 이상 마지막에 가서는 1,2,3으로 추려진다.