[Kotlin] 백준 11866 : 요세푸스 문제 0

문제 링크

11866번: 요세푸스 문제 0

---

---

문제 해설

문제의 예시를 그림으로 나타내면 다음과 같다.

그림을 보면 다음에 나갈 사람의 위치는 시작 위치 + \(k\) - 1인 것을 알 수 있다. 즉, 다음 순서로 나갈 사람의 위치는 이전에 나간 사람의 위치에 \(k-1\)을 더하면 된다. 이제 남은 사람의 수가 \(k\)보다 작아졌을 때의 처리만 하면 되는데, 이 때는 앞에서 구해진 다음 순서로 나갈 사람의 위치가 남은 사람의 수보다 작아질 때까지 남은 사람의 수를 빼주면 된다.

 

나간 사람의 번호는 별도의 배열에 저장하고 문제의 조건에 맞는 형태로 출력하면 된다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val circle = ArrayList<Int>()
    val josephus = ArrayList<Int>()
    var next = 0
    repeat(n) {
        circle.add(it + 1)
    }
    while (circle.isNotEmpty()) {
        next += k - 1
        while (next > circle.lastIndex) next -= circle.size
        josephus.add(circle.removeAt(next))
    }
    println("<${josephus.joinToString()}>")
}