[BOJ 5904] Moo 게임

문제 링크 : https://www.acmicpc.net/problem/5904

본문

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 

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번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 10⁹)이 주어진다.

출력

N번째 글자를 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

Moo 수열은 이미 결정되어있다. 우리가 찾아야 하는 $N$은 최대 $10^9$번째 글자이므로, $S(k)$의 길이를 미리 계산해두면 편할 것 같다. 우선, $S(k)$의 길이 $l(k)$를 계산할 때, 점화식을 아래와 같이 정의할 수 있다.

\[l(k) = 2 \times l(k-1) + (k + 3) \quad \forall k \geq 0\]

이 식을 통해 계산해보면, $l(27)$에서 처음으로 $10^9$을 넘어가는 것을 계산할 수 있다. 정확히는 $1\,073\,741\,792$글자라고 한다. 즉, 찾으려는 문자는 항상 $S(27)$ 안에 존재하므로, 탐색할 범위를 줄일 수 있다.

이제 찾으려는 문자 $c$의 위치를 특정할 방법을 생각해보자. 수열 $S(k)$는 아래와 같이 재귀적으로 이루어져있다.

\[S(k) = S_{front}(k-1) + moo\cdots + S_{back}(k-1)\]

우리는 여기서 $S(k)$의 길이 $l(k)$를 모두 계산해두었으므로, 수열 $S(k)$를 3개의 부분으로 쪼갠 다음, 문자 $c$가 어느 부분에 들어있는지 알 수 있다. 앞의 수열과 뒤의 수열의 구분을 위해 앞의 수열을 $S_{front}$, 뒤의 수열을 $S_{back}$이라고 하자. 수열의 시작점으로부터의 거리 $IDX_c$를 계산하고, 아래와 같은 조건을 적용해보면 된다.

• $IDX_c < l(k-1)$인 경우 : 문자 $c$는 수열 $S_{front}$에 속해있다
• $IDX_c \geq l(k) - l(k-1)$인 경우 : 문자 $c$는 수열 $S_{back}$에 속해있다
• 나머지 경우 : 문자 $c$는 중앙 부분에 속해있다
  • 이 경우, 문자 $c$가 ‘m’인지 ‘o’인지 판단해야한다. 중앙 부분의 가장 앞이 ‘m’, 나머지는 모두 ‘o’이므로, $c$의 위치 $IDX_c$를 토대로 판별해낼 수 있다

즉, 이 문제는 “수열을 분할하여 나눌 수 있는가”와 “각 수열의 길이를 미리 계산할 수 있는가”, 그리고 “문자 $c$가 각 수열에서 어느 부분에 포함되어있는가”를 알아내면 해결할 수 있는 분할정복 알고리즘 문제이다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분할정복 알고리즘