[백준 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)
}
}
Author And Source
이 문제에 관하여([백준 5904 - Kotlin] Moo 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-5904-Kotlin-Moo-게임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)