2292번: 벌집

문제 출처 : https://www.acmicpc.net/problem/2292

2292번: 벌집

언어 : Kotlin

 

문제 설명 :

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

• 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
• 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
13	3

풀이 : 

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

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

    if (n == 1) {
        bw.write("${1}")
    } else {
        var room = 2
        var num = 1

        while (room <= n) {
            room += 6 * num++
        }

        bw.write("$num")
    }

    bw.flush()
    bw.close()
}

1 - 1
2 - 2 .. 7
3 - 8 .. 19
4 - 20 .. 37
5 - 38 .. 61

 

시작점 기준 : 1 - 2 - 8 - 20 - 38
끝점 기준 이전 끝점과 차이 : 1 - 6 - 12 - 18 - 24

다음 방 시작점을 아는 방법은 시작점 + 6 * k 규칙을 갖는다.

 ex) 2 + 6 * 1 = 8

 

막혀서 돌아가거나 하는 제한이 없기 때문에 모든 방은 지나갈 수 있다.

따라서 1번 방에서 해당하는 n번 방까지 지나가는 방의 개수 k를 구하면 된다.

 

S 시작지점을 기준으로 둘러쌓인 방을 k층으로 생각해보자