[백준] 2292번 - 벌집 (Java)

문제

https://www.acmicpc.net/problem/2292

2292번: 벌집

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int layer = 1;
        int max = 1;

        while (true) {
            // n이 이번 층의 최대값 보다 작다면 해당 층에 포함되어 있는 것.
            if (n <= max)
                break;
            
            // 다음 층 최대값 세팅, 이동
            max += (6 * layer);
            layer++;
        }

        System.out.println(layer);
    }
}

 

각 층의 수 개수

1에서 번호n까지 오는 최단루트는 1에서 각 층을 바로 가로질러 가는 것이다. 일단, 벌집을 아래와 같이 층(layer)으로 구분한다. 1층(1), 2층(2~7), 3층(8~19), 4층(20~37), 5층(38~61) … 이런 식으로 구분하면 각 층의 번호 갯수가 첫째항이 1, 공차가 +6 인 등차수열 { 1, 6, 12, 18, 24, … } 임을 확인할 수 있다.

각 층의 최대값

각 층의 번호 갯수가 일정한 크기 만큼 증가하므로 각 층(layer)의 최대값 또한 일정한 규칙을 가지고 정해질 것이다. {1, 7, 19, 37, 61, … } 첫째항 1부터 시작해 차례로 6(6*1), 12(6*2), 18(6*3), 24(6*4) 만큼 값이 증가한다.

이렇게 구한 규칙을 토대로 한층 한층 최대값을 구해, n이 해당 최대값의 범위에 포함되는지(현재 층의 최대값 보다 작거나 같은지)를 체크해나간다. 위 조건에 부합할 경우 해당 최대값이 포함된 층에 위치한 값이라는 뜻이므로 반복을 중단(break)하고 현재 layer 값을 반환한다.