백준 5904. Moo 게임

https://www.acmicpc.net/problem/5904

5904번: Moo 게임

 

k 일때 문자열의 길이는 다음과 같다.

S(k) = S(k-1) + (k+3) + S(k-1) 

 

문자열은 총 세가지 구간으로 분할 가능하다.

 

k=2 일때의 문자열 = (1)MOOMOOOMOO (2)MOOOO (3)MOOMOOOMOO

k 값을 늘리면서 우리는 S(k)의 길이 len을 위의 식으로 구할수 있다. 

k 값을 늘려가며 len 을 구하다가 만약 내가 구하는 N번째가 len 에 포함되면 현재 문자열에서 답을 구할수 있다는 뜻이다.

 

그렇다면 (1)~(3) 구간 중에 어딘지를 판단해본다.

그런데 생각해보면 (1) 구간은 k-1 에서  (즉 이전 재귀에서) 이미 탐색을 했기 때문에 현재 재귀까지 도달했다는 것은 절대로 내가 찾는 N이 (1) 구간은 아니라는 뜻이다.

 

따라서 (2) 아니면 (3) 인데, 

(2) 구간일 경우, (2) 구간의 첫글자일 경우만 m 이고 나머지는 o 라는 것을 알 수 있다.

 

(3) 구간일 경우, 이 부분이 이 문제의 핵심이라고 볼 수 있는데

(3) 구간일 경우에는 재귀를 처음부터 다시 시작해야한다. 

예를들어 (1)MOOMOOOMOO (2)MOOOO (3)MOOMOOOMOO 에서 N이 3단계에 속한다고 판단될 경우 

MOOMOOOMOO 를 대상으로 처음부터 재귀를 다시 시작하면 된다.