백준 5904 - Moo 게임

Java

5904 번 - Moo 게임

문제

Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o 

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 “m o o”이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 “m o … o” 와 S(k-1)을 합쳐서 만들 수 있다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.

N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

접근 방법

코드

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

public class Main {
	static int n, result;
	static ArrayList<Integer> mooCnt = new ArrayList<>();
	static ArrayList<String> moos	= new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = stoi(br.readLine());
    	
    	mooCnt.add(3);			// 
    	moos.add("moo");
    	int num;
    	while(mooCnt.get(mooCnt.size() - 1) < n) {
    		moos.add(moos.get(moos.size() - 1) + "o");
    		num = mooCnt.get(mooCnt.size() - 1);
    		mooCnt.add(num + moos.get(moos.size() - 1).length() + num);
    	}
    	Mooo(n - 1, mooCnt.size() - 1);
    	br.close();
	}
	static void Mooo(int num, int idx) {
		// "moo"만 남은 경우
		if(num < 3) {
			System.out.println(moos.get(0).charAt(num));
			return;
		}
		// 왼쪽 S(k-1) 인 경우
		if(num < mooCnt.get(idx - 1)) {
			Mooo(num, idx - 1);
		}
		// 사이의 "mooooo" 인 경우
		else if(mooCnt.get(idx-1) <= num && num < mooCnt.get(idx-1) + moos.get(idx).length()) {
			System.out.println(moos.get(idx).charAt(num - mooCnt.get(idx-1)));
			return;
		}
		// 오른쪽 S(k-1) 인 경우
		else {
			Mooo(num - mooCnt.get(idx - 1) - moos.get(idx).length(), idx - 1);
		}
		return;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

개선할 점