[백준 5904번] Moo 게임

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

5904번: Moo 게임

Moo 게임은 골드 5 문제로 분할 정복을 이용해서 푸는 문제입니다

---

Moo 게임?

MOO는 길이가 무한대인 수열입니다. 그렇기 떄문에 수열을 생성하는데 규칙이 있는데 이건 다음과 같습니다

 

1.S(0)="m o o" 이다
2.S(k)=S(k-1)+"m"+"o * (k+2)"+S(k-1) 이다

---

풀이

이 문제만 보고 어? 배열로 다 만들어놓고 몇번째인지 세면 되는거 아니야? 라고 생각하는 분들도 계실수 있습니다. 하지만 조건을 보면

이처럼 N이 10^9까지 가기때문에 배열을 만드는 식으로 하면 메모리 초과 오류가 발생하게 됩니다. 그래서 해당 자리에 M이 올지 O가 올지, 판단하는 식으로 문제를 풀면 되겠습니다 예를 들어 9번째 자리에 뭐가 들어가는지 볼려합니다. 

그 경우 맨 초기값 S(0)은 이렇습니다

m

o

o

자 여기서, 다음 S(1)은 규칙에 의해서 m o o 다음에 4번째에 들어갈 글자는 m인것을 알 수 있습니다. 그리고 다음에는 o가 k+2만큼 들어가기에 

m

o

o

m

o

o

o

인것을 알수 있습니다. 그 다음에는 "m o o" 가 차례대로 들어가 9번째 자리는 o인것을 알수 있습니다. 하지만 저희가 생각할 때는 곧바로 접근할수 있지만 코딩을할때는 어떻게 해야할지 감이 안잡힐수도 있습니다. 이 단계까지 왔는데, 아직 공간이 남았다면 다시 이 재귀함수를 호출할때, 찾아야할 값과 S(k-1)+"m"+"o*(k+2)" 까지의 길이를 빼주고,  S(k-1) 단계로 돌아와서 빼준 값의 위치에 뭐가 들어있는지 알아내면 됩니다.

예를 들어 위의 표같은 경우는 찾아야할 값이 9이고, S(k-1)+"m"+"o*(k+2)"의 길이는 7이므로 S(0)단계로 돌아가서, 2번째 인덱스에 위치한 단어를 찾으면 됩니다. 

m

o

o

이 경우 S(0)의 두번째 자리인 o 임을 알수 있습니다

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Moo {
	public static void main(String args[]) {

		//입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        try {
			int n=Integer.parseInt(br.readLine());
			int moo_num=3;
			bw.write(GetMoo(n,moo_num,1));
			bw.flush();
			bw.close();
		
			
		} catch (NumberFormatException e) {
			
			e.printStackTrace();
		} catch (IOException e) {
			
			e.printStackTrace();
		}
	}
	
	public static String GetMoo(int n,int prev_moo,int count) {
		//만약 3미만인경우는 초기값에서 찾으면 되니 바로 찾아준다
		if(n<=3) {
			if(n==1)
				return "m";
			else
				return "o";
				
		}else {
			//다음 단계의 moo 수열 값을 저장
			int new_moo=2*prev_moo+count+3;
			//만약 찾고자하는 값이 다음단계의 +count+3만큼 작고, 다음단계의 수열단계보다 크면, 다음단계의 moo수열을 재귀로 호출하고, 아니라면 (count-1)단게의 값만 남겨놓고 다시 계산한다,
			if(prev_moo+count+3<n)
				if(n<new_moo) {
					return GetMoo(n-(prev_moo+count+3),3,1);
				}
				else {
					count++;
					return GetMoo(n,new_moo,count);
				}
			else { 
				if(prev_moo+1==n)
					return "m";
				else
					return "o";
			}
		}
		
	}
}