설명
Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 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
Plain Text
복사
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"
Plain Text
복사
위와 같은 식으로 만들면, 길이가 무한대인 문자열을 만들 수 있으며, 그 수열을 Moo 수열이라고 한다.
N이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 10^9)이 주어진다.
출력
N번째 글자를 출력한다.
예시 입력
예시 출력
11
JavaScript
복사
m
JavaScript
복사
풀이 과정
해당 문제는 문자열의 점화식을 파악하는 것이 관건입니다. 문자열은 다음과 같은 패턴으로 변화합니다.
S(k) = S(k-1) + mo…oo + S(k-1)
이 문제의 입력은 10^9 까지 이므로 단순하게 접근해서는 절대 풀리지 않습니다.
예를 들어, String moo = moo + (mo…o) + moo; 이런식으로 10^9 개의 문자를 합치고, chatAt()으로 구한다는 방법은 먹히지 않습니다 (바보 같이 했다가,, 
)
)S(2) 문자열을 가져와 보겠습니다.
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"
SQL
복사
핵심은 Moo 문자열은 다음과 같이 나눌 수 있다는 점입니다.
•
앞의 Moo = moomooomoo
•
중간의 Moo = moooo
•
뒤의 Moo = moomooomoo
이렇게 구역을 나누었을 때 좋은 점은 N이 어느 Moo에 위치해있느냐에 따라 해당 인덱스의 문자를 유추할 수 있다는 점입니다.
예를 들어, N이 중간 Moo 에 위치해 있다고 가정합니다.
중간 Moo는 맨 앞의 m을 제외한 나머지 문자는 전부 o입니다. 맨 앞의 m은 앞의 Moo의 바로 뒤 인덱스입니다. 앞 전의 점화식을 기억하시나요?
S(k) = S(k-1) + mo…oo + S(k-1)
우리는 S(k-1)을 가지고 S(k)를 구합니다. S(k-1)은 위에서 말하는 앞의 Moo 문자열이 되겠죠. 즉, 앞의 Moo 문자열의 길이를 이미 알고 있으니, 앞의 Moo 문자열 길이 +1에 해당하는 인덱스가 m 나머지가 o 입니다.
만약 앞의 Moo 혹은 뒤의 Moo에 N이 위치해 있다면 어떨까요? 재귀적으로 풀면 됩니다. 위의 예제를 이어 설명해보면 앞의 Moo 인 moomooomoo 또한 다음과 같이 나눌 수 있습니다.
•
앞의 Moo = moo
•
중간의 Moo = mooo
•
뒤의 Moo = moo
이 과정에서 N의 위치를 파악하여 위와 동일하게 계산을 이어나가면 됩니다.
최종 코드
package baekjoon.divide_and_conquer;
import java.util.Scanner;
public class _5904 {
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
// Initialization
int length = 3;
int prev = 3;
int k = 0;
// n의 범위를 구해주기
while (length < N) {
k++;
prev = length;
length = 2 * prev + (1 + 2 + k); // S(K-1) * 2 + (moo...o)
}
Moo(length, k);
}
private static void Moo(int length, int k) {
int prev = (length - (1 + 2 + k)) / 2; // 중간을 제외한 moo 크기를 구함
if (k == 0) {
if (N == 1) {
System.out.print("m");
return;
} else {
System.out.print("o");
return;
}
}
if (N <= prev) {
Moo(prev, k - 1);
} else if (prev + 1 <= N && N < prev + (1 + 2 + k)) { // prev + (moo...o)
if (prev + 1 == N) {
System.out.print('m');
} else {
System.out.print('o');
}
} else { // 앞 쪽에 있거나 뒤 쪽에 있는 경우
N -= (prev + (1 + 2 + k));
Moo(prev, k - 1);
}
}
}
JavaScript
복사
