[백준 5904] Moo 게임 (Kotlin)

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

5904번: Moo 게임

문제

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^9)이 주어진다.

 

출력

N번째 글자를 출력한다.

 

알고리즘 분류

• 분할 정복
• 재귀

---

해설

우선 처음에는 가장 전형적인 재귀 방식을 통하여 문제를 풀어보았다..

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))

    val seq = br.readLine().toInt()

    var str = mooGame(seq / 3)

    println(str[seq - 1])
}

private fun mooGame(cnt: Int): String{
    if(cnt == 0){
        return "moo"
    }

    var makeStr = "m"

    for(i in 0 until cnt + 2){
        makeStr += "o"
    }

    return mooGame(cnt - 1) + makeStr + mooGame(cnt - 1)
}

 

결과는 당연하게 시간초과(메모리 초과)….

 

어떻게 하면 메모리 초과가 안날지 열심히 생각해보았는데 분할정복이 생각났다!👍

 

우선 위 방식처럼 문자열을 사용하는 것이 아닌, 문자열의 길이를 사용하였다.

 

우선 전체 코드부터 보여주겠다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val input = br.readLine().toInt()

    mooGame(input, 1, 3)
}

private fun mooGame(input: Int, cnt: Int, len: Int){
    val newLen = 2 * len + cnt + 3

    if(input <= 3){
        if(input == 1){
            println("m")
        }else{
            println("o")
        }

        return
    }

    if(newLen < input){
        mooGame(input, cnt + 1, newLen)
    }else{
        if(len < input && input <= len + cnt + 3){
            if(input - len == 1){
                println("m")
            }else{
                println("o")
            }
        }else{
            mooGame(input - (len + cnt + 3), 1, 3)
        }
    }

}

 

newLen = 2 * len + cnt + 3 의 의미는 기존 문자열 * 2 + k + 2(”o”의 개수) + 1(”m” 한개) 이다.

 

위의 방식처럼 새로운 길이의 변수를 만들고 기존 input값과 비교하였다.

 

총 3번의 비교를 하는데

1. input값이 newLen의 길이보다 클 때이다.
2. input값이 S(k - 1)사이의 “m…(k + 2개의 o)” 즉, o가 k+2개인 수열안에 있을 때다.
3. input값이 뒤쪽의 S(k - 1)안에 있을 때다.

첫 번째 경우일때는 mooGame(inp, k + 1, nLn) newLen < input 를 실행시켜 만족할 때 까지 길이를 늘려준다.

 

두 번째 경우일때 가운데 o가 k+2개인 수열안 에 있기에 input - len == 1 일 경우 m을, 아닐 경우 o를 출력한다.

 

input - len 의 의미는 input의 길이에 이전 문자열의 길이 즉, 앞쪽 S(k - 1)의 길이를 빼주는 것이다.

 

세 번째 경우는 input의 값을 input - (len + cnt + 3) 으로 바꿔준다.

즉, input의 값을 앞쪽 S(k - 1) + o가 k+2개인 수열의 길이 를 빼준 것이다.

 

그 후 처음부터 다시 함수를 실행하여 값을 출력한다.