BOJ 5904 Moo게임

1. 변수

   int N // N 번째 문자 뽑기
   ArrayList<Integer> arr // s(0) 부터 해당 문자열 size 담는 배열
   

2. 구현로직

   1. reculsive

   2. size로 접근

3. 코드

   package baekjoon.Silver;
      
   import java.io.BufferedReader;
   import java.io.InputStreamReader;
   import java.util.ArrayList;
      
   public class BOJ_5904_Moo게임 {
   	private static int N;
      
   	public static void main(String[] args) throws Exception {
   		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   		N = Integer.parseInt(br.readLine());
      
   		ArrayList<Integer> arr = new ArrayList<Integer>();
      
   		arr.add(3); // arr.get(0) = 3
      
   		for (int i = 1; i < Math.pow(10, 9); i++) {
   			int temp = arr.get(i - 1) + i + 3 + arr.get(i - 1);
   			arr.add(temp);
   			if (N <= temp) {
   				dfs(i, temp);
   				break;
   			}
   		}
   	}
      
   	private static void dfs(int k, int temp) {
   		if (k == 0 || N <= 3) {
   			if (N == 1) {
   				System.out.println('m');
   				return;
   			} else {
   				System.out.println('o');
   				return;
   			}
   		}
   		int num = (temp - k - 3) / 2; // 기준이 되는 수
      
   		if (N <= num || num + k + 3 < N) { // 반복되는 부분에 N이 들어있으면
   			N = N % (num + k + 3);
   			dfs(k - 1, num);
   		}
      
   		else { // 가운데 k+2에 N이 들어있으면
   			if (N == num + 1) {
   				System.out.println("m");
   				return;
   			} else {
   				System.out.println("o");
   				return;
   			}
   		}
   	}
   }
      
   

4. 느낀점

   • 문제…는 S(N)이 아니라 N번째 글자를 뽑는 거였다는거였다는것이엇다… * 재귀 공부를 더 열심히 해야겠다..
   • 시간 엄~~청 오래걸렸음..

문제 링크 : 백준 5904 Moo 게임