[Rust로 백준 하루 하나] 8-5. 벌집

문제 (2292번)

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

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

---

풀이

코드

use std::io;

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    let n: i32 = n.trim().parse().unwrap();
    
    let mut k: i32 = 1;
    loop {
        if n == 1 {
            break;
        } else if 3*(k-1)*(k-1) - 3*(k-1) + 1 < n && 3*k*k - 3*k + 1 >= n {
            break;
        } else {
            k += 1;
        }
    }
    println!("{k}");
}

해설

벌집의 구조상 주어진 입력이 몇 번째 층에 있는지를 구하면 몇 개의 방을 지나는지 알 수 있다. 어떤 방이든 벌집의 중심(1)으로 부터 해당 방에 접해있는 아래 층의 방까지 이어질 수 있기 때문이다.

벌집 각 층의 마지막 숫자는 다음과 같은 계차수열이다.
$6, 12, ... : b_n = 6n$
$1, 1+6, 1+6+12 ... : a_n = 1 + (6+12+ ... + 6(n-1))$
$= 1 + 6 * n(n-1)/2 = 3 n^2 - 3n + 1$

---

추가 학습

• 계차수열
  https://m.blog.naver.com/fordusrk23/221533734511