백준코딩 [2292] 벌집 - Kotlin

2292번 벌집문제는 흔히 수학에서의 최단거리 문제와 비슷했다.

 

벌집 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 할당, 중앙방 1부터 목적지방 N까지 최소개수의 방을 지나서 갈때 지나가는 방의 갯수를 묻는 문제다.

 

이 문제는 엄밀히 말하면 수학에서 수열(Sequence)와 관련이 있다. 벌집 방의 번호 할당 방식이 중앙방 1 부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 규칙인데, 이것은 엄밀히 말하면 계차수열이라고 볼 수 있다. 벌집은 육각형이기에 중앙방을 기준으로 이웃하는 방들을 한 껍질(Shell)로 묶어보면 각 껍질(Shell)의 마지막 방 번호는 1 - 7 - 19 - 37 - 61 ...... 이렇게 진행된다. 이 숫자들의 공차는 6 - 12 - 18 - 24 ......이며 이것은 일반항이 6n인 등차수열이다. 공차가 등차수열인 수열, 즉 계차수열이다.

 

처음에는 목적지방 번호 N을 받아서 공차의 일반항인 6n을 적용해 빼가는 방식을 사용했었다. 계산에서는 문제가 없었고, 백준코딩 사이트에서 제시한 예시 답안도 올바르게 출력됬었다. 그런데 답안을 제출하니 오답이였다.

 

하나하나 문제 가능성이 있는 숫자들을 대입해보며 확인했더니, 7이나 19와 같은 껍질의 마지막 번호 방이 목적지 방으로 입력이되면 이동거리가 1씩 증가해서 출력되는 것을 확인하였다. 그래서 목적지 방에서 공차를 차례차례 빼는 방식 대신, 1부터 시작해 공차를 차례차례 더해가는 방식, 즉 계차수열을 그대로 따라가기로 했다. 계차수열에서 1항씩 증가하는 것은 껍질(Shell)이 한개씩 증가한다는 것이며, 말 그대로 최단거리로 이동시 필요한 방 개수가 하나씩 는다는 의미기 때문에, while문 안에서 계차수열을 계산하여 lopp를 한번씩 돌때마다 Shell의 개수도 1개씩 증가시켰다. while문의 조건은 roomNumber < destination 으로 설정해서 목적지 방이 몇번째 껍질(Shell)안에 있는지 얻어낼 수 있게 했다.

 

 

 

 

import java.io.InputStreamReader
import java.io.BufferedReader
 
fun main(arg: Array<String>) {
    val usrBufferedReader = BufferedReader(InputStreamReader(System.`in`))
    var destination = usrBufferedReader.readLine().toInt()
    var numberOfShell = 1
    var roomNumbers = 1
 
    if(destination == 1) {
        println(1) //Since the destination is 1, bee doesn't need to move.
    } else {
        while (roomNumbers < destination) {
            roomNumbers += (numberOfShell * 6)
            numberOfShell++
        }
        println(numberOfShell)
    }
}