[BOJ 분할정복] Moo 게임 5094.JAVA

문제 링크 : https://www.acmicpc.net/problem/5904

5904번: Moo 게임

---

Moo 게임 문제를 접했을 때 메모리 제한을 간과하고 moomooomoo... 이런 식으로 문자열을 만들었다.
하지만 메모리 초과가 발생하여 다시 풀었지만 접근조차 하지 못했다.
문제 자체는 이해하기 쉽지만 구현해 내기에는 센스가 필요하다고 생각됐다.
결국 그 센스를 발휘하지 못하여 상당히 분했지만 이런 유형의 문제를 익힌다는 마음으로 학습하고 머릿속에 각인시켰다.

 

아래와 같이 소스를 공유 합니다.

import java.util.Scanner;

public class Main {
    public static String ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        moo(n);
        
        System.out.println(ans);
    }
    
    public static void moo(int num) {
        int side = 3;
        int center = 0;
        
        while(num > side) {
        	// 4를 더하는 이유는 두번째 수열을 더하기 위함
            side = center + 4 + side * 2;
            center++;
        }
        
        // 3을 빼주는 이유는 while문에서 center는 1씩 증가해서
        // center+4가 실제 가운데 영역보다 1크기 때문에 
        int fb = (side - center - 3) / 2;
        
        if(side - fb+1 <= num) {
            moo(num - side+fb);
        }else if(num == fb+1) {
            ans = "m";
        }else {
            ans = "o";
        }
    }
}