Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.
Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.
위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다. N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.
설명
입력되는 index의 문자를 알기위해선 해당 배열을 알아야 하는데 배열을 만들자니 배열의 크기가 최대 1000000000개라 보나마나 메모리 초과가 날 것이다. 그렇다고 무작정 재귀를 통해 들어가자니 시간초과가 날 것이다. 아예 다른 시각이 필요하다.
Moo 수열 전체를 구해서 N의 절대 위치를 찾는게 아닌 Moo 수열을 계속 쪼개가며 N과의 상대 위치를 찾는다.
일단 N보다는 긴 Moo 수열이 필요하다. Moo 수열은 가운데 오는 "moo..."와 양쪽에 이전 Moo수열이 온다. 따라서 k번째 Moo수열 S(k)는 다음과 같은 점화식을 같는다.
S(k) = S(k-1)*2 + (k+2)
위 점화식을 통해 필요한 Moo 수열의 최소 길이를 구한다.
m o o m o o o m o o
m o o o o o
m o o m o o o m o o
Moo수열은 위와 같은 패턴이 재귀적으로 반복된다. 위 배열에서 각각을 좌Moo, 중Moo, 우Moo라고 하자. 만약 N이 중Moo에 온다면 N과 중Moo 사이에 상대경로를 통해 N번 째 문자를 구할 수 있다.
만약 N이 좌Moo 또는 우Moo에 온다면 새로운 N과 Moo수열을 구할 수 있다.
m o o
m o o o
m o o
만약 N이 좌Moo에 왔다면 N의 크기는 그대로이고 k가 1 줄어든 새로운 비교가 만들어진다. 만약 N이 우Moo에 왔다면 N의 크기는 S(k)+(k+2)만큼 줄어들고 k는 1줄어든 새로운 비교가 생긴다. 이런식으로 N이 중Moo에 올 때까지 반복하면 N과 Moo수열 사이의 상대 경로를 찾을 수 있다.
코드
//5904번 Moo 게임.java
package week7;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Moo_게임_5904 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N;
static int now;
static int preNow;
static int mid;
public static void main(String[] args) throws NumberFormatException, IOException {
N = Integer.parseInt(br.readLine());
preNow=0;
now=3;
mid=3;
while(N > now) {
preNow = now;
now = now*2+(mid+1);
mid++;
}
while(true) {
if(preNow < N && N <= preNow+mid) {
N -= preNow;
break;
}
if(N <= preNow) {
now = preNow;
mid--;
preNow = (now-mid)/2;
}
else {
now = preNow;
N -= (preNow+mid);
mid--;
preNow = (now-mid)/2;
}
}
if(N==1)System.out.println('m');
else System.out.println('o');
}
}
