[백준 5904 - Kotlin] Moo 게임

문제링크

• n의 위치가 S(i)에 존재한다고 가정해봅시다.
• S(i)는 S(i - 1) + mooo... + S(i - 1) 을 의미하고,
• n의 위치가 S(i)에 존재한다는 것은 S(i - 1)에는 존재하지 않다는 것을 의미합니다.
• 따라서 S(i)에 존재한다는 것을 알게되었을 때 우리가 고려해야 할 구간은 mooo... + S(i - 1) 구간 입니다.
• 먼저 mooo... 구간에 존재하는 것을 찾기 위해선 n이 (S(i)의 길이 - S(i - 1)의 길이) 보다 작거나 같을 때의 조건을 확인해야 합니다.
• 만약 n의 위치가 S(i - 1) 구간에 존재한다면, S(i - 1) 구간을 시작점으로 생각하여 n의 상대적인 위치를 변경시키고 다시 처음부터 변경된 n이 존재하는 구간을 찾아줍니다.

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    // 1. get n
    val n = bufferedReader.readLine().toInt()

    // 2. print Nth letter
    findNthLetter(n, 1, 3)

    bufferedReader.close()
    bufferedWriter.close()
}

fun findNthLetter(n: Int, k: Int, baseLength: Int) {
    if (n == 1) {
        bufferedWriter.write("m")
        return
    }

    if (n == 2 || n == 3) {
        bufferedWriter.write("o")
        return
    }

    val mid = k + 3 //◀ o는 (k + 2)개 이고, m 까지 포함하면 (k + 3)을 해주어야 합니다.
    val total = baseLength * 2 + mid
    if (n > total) {
        findNthLetter(n, k + 1, total)
        return
    }

    // moomooomoo 일 때, n의 위치가 mooo에 위치하는지 확인하는 조건문 입니다.
    if (n <= (total - baseLength)) {
        if (n - baseLength == 1) bufferedWriter.write("m")
        else bufferedWriter.write("o")
    } else {
        // n의 위치가 뒤에 있는 moo에 위치할 때, n의 상대적 위치를 변경시키고 처음부터 재귀를 시작합니다.
        findNthLetter(n - (baseLength + mid), 1, 3)
    }
}