kingsubin

import java.util.Scanner;
 
public class boj_5904 {
    static Scanner sc = new Scanner(System.in);
    static int[] dp = new int[30];
 
    public static void main(String[] args) {
        int N = sc.nextInt();
 
        dp[0] = 3;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = (dp[i-1]*2) + (i + 3);
        }
 
        System.out.println(func(N));
    }
 
    static char func(int n) {
        if (n == 1) return 'm';
        if (n == 2 || n == 3) return 'o';
 
        int i = 0;
        while (dp[i] < n) i++;
        if (dp[i] == n) return 'o'; // 끝
        if (n - dp[i - 1] == 1) return 'm'; // 다음 칸
        if (n - dp[i - 1] <= i + 3) return 'o'; //  moo.... 에서 o 해당하는 칸
 
        return func((n - dp[i - 1] - (i + 3)));
    }
 
}
 

 

- 재귀, dp

- 길이 구하는 점화식이랑 규칙은 눈에 보이는데 함수 식을 어떻게 세울지 생각이 안났다.

- 어려움

 

 

- 길이는 주어진 식대로 S(k) = S(k-1) * 2 + (3 + k) 로 구할 수 있고 거의 2배씩 늘어나고 2^30 >= 10억

이니까 dp에 길이를 30까지만 저장해준다,

- base condition 으로 'moo' 에 맞게 설정한다.

- int i 값을 이용해서 지금 n이 S의 몇번째 index인지 찾아준다.

- S(k-1) | m o o .... | S(k-1) 에서 m o o .... 에 해당하는 부분을 따로 처리해주고 해당하지 않으면

n - dp[i-1] - (i+3) 을 다시 호출한다.

 

 

 

---

www.acmicpc.net/problem/5904