[JAVA]백준 5904번: Moo 게임

[JAVA] 백준 5904번: Moo 게임

 

 

백준 5904번

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

 

 

문제

 

문제는 이해하기 쉽다.

 

moo 들의 조합으로 이루어진 문자열의 규칙을 찾아서,

입력되는 N번째의 문자가 어떤 문자('m' 또는 'o')인지 출력하면 된다.

 

보면 규칙적으로 m은 단어의 첫 번째에서만 나온다.

규칙 찾고, 첫 번째 단어인지 체크 → 맞으면 'm', 아니면 'o'를 출력하면 끝

 

이제 규칙을 찾아보자

 

규칙

 

문자열이 길어지는 규칙을 보면

S[k] = S[k-1] + moo+o(k) + S[k-1]* 이다.

즉, 가운데를 기준으로 앞, 뒤에 이전 값이 붙는다.

 

 

이를 토대로

 

 

입력된 숫자(N)가 10 정도 된다고 가정했을 경우,

수많은 moo 들을 크게

왼쪽 moo(Left) / 가운데 moo(Middle) / 오른쪽 moo(Right) 들로 나누어 보았다.

 

 

예시 > S(1) = "m o o / m o o o / m o o"

왼쪽 moo(Left) / 가운데 moo(Middle) / 오른쪽 moo(Right)

 

 

 

위와 같이 나누어 생각한 후 입력된 N의 범위가

어디에 해당하는지 판별한다.

그리고 해당하는 범위로 재귀를 호출해준다.

 

 

(가장 작은 moo는 'moo' 이기 때문에 moo까지 쪼개졌으면 종료)

 

---

 

👆🏻N의 범위 : 1 ≤ N ≤ 10^9

(N의 크기를 보면, 이분 탐색을 통해 크기를 절반씩 줄여나가며 탐색해야 시간 복잡도를 줄일 수 있다)

💡아이디어 : 이분 탐색

(이분 탐색은 보통 재귀 함수로 구현)

(장점: 구현과 가독성이 좋다)

✍🏻점화식

S[k+1] = S[k] + (4+k) + S[k];

(4+k) 는?

예시 > S(1) = "m o o / m o o o / m o o"

(1(m의 개수) + 2(o의 기본 개수) + k+1) ⇒ k+4

 

 

재귀 함수 구조

private static char moo(범위){

//기저조건
if(범위가 3이하인 경우){
	return 'm' or 'o';
}else{
	// N 이 왼쪽 영역인 경우
	return moo(Left);
	
	// N 이 오른쪽 영역인 경우
	return moo(Right);
	
	// N 이 가운데 영역인 경우
	return 'm' or 'o';

	}

}

 

[JAVA] 해설 코드

package week06;

import java.util.Scanner;

public class BOJ_5904 {

	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		// S[0]일 때, 문자열의 총 길이 
		int num = 3;
		// S[k-1]의 마지막 index
		int preK = 3;
		// index
		int k = 0;
		
		//  n의 범위를 구해주기
		while(num<n) {
			k++;
			num = 2 * preK + (1+2+k);
			preK = num;
		}
		// 재귀함수에 시작값으로 넣어주기 위해 preK 을 다시 구함
		preK = (num-(1+2+k))/2;
		
		
		char c=' ';
		
		// 입력된 숫자가 3 이하일 경우
		if(k==0) {
			if(n==1)c = 'm';
			else c = 'o';
		}else {
			// 3보다 클 경우
			if(preK+1<=n && n<preK+(1+2+k)) {
				if(preK+1==n) {
					c =  'm';
				}else c = 'o';
			}else
				c = moo(preK+1+(1+2+k),k-1,num);
		}	
		
		System.out.println(c);
		
	}
			// 시작 index, k 값, 끝 index
	private static char moo(int si, int k, int se) {
		
		// 중간 moo의 크기 구하기
		int index = ((se-si+1 -(k + 3))/2);
		
		// 기저조건
		if(k==0) {
			if(n==si) return 'm';
			else return 'o';
		}else {
			
			//왼쪽인 경우
			if(si<=n && n<si+index) {
				if(si==n) return 'm';
				return moo(si, k-1, si+index-1);
				//else return 'o';
			}
			//오른쪽인 경우
			else if(si+index+(k + 3)<=n && n<=se) {
				if(si+index+(k + 3)==n) return 'm';
				else return moo(si+index+(k + 3), k-1, se);
			}
			//가운데
			else{
				if(si+index==n) return 'm';
				else return 'o';
			}
		}

		
	}

}

 

메모리와 시작은 이 정도 나왔다.

 

 

 

 

추후에 이 문제를 더 보기 쉽고 간결하게 다시 짜 볼 생각이다.