[백준/JAVA] 반복문을 사용하지 않는 2292번 벌집

• 벌집이 형성되는 규칙에 따라 벌집의 위치를 구하는 문제
  https://www.acmicpc.net/problem/2292

1. 문제

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

2. 문제 접근

• 입력의 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
• 단, 반복문을 사용하면 시간 복잡도가 커지니 문제에서 규칙을 찾아서 수학적으로 계산할 수 있도록 유도하자!!

핵심!

• 출력 값에 따라 입력 값들을 나누어 보자.

출력 값

• 1 -> 1
• 2 -> 2~7
• 3 -> 8~19
• 4 -> 20~37
• 5 -> 38~61

입력 값들을 살짝 조작해보자. 1을 빼고 6으로 나누어보자.

출력 값

최소 지나는 방의 개수	방숫자의  범위	(방숫자 -1 ) / 6	0부터 최소 지나는 방의 개수 -1 까지의 합
1	1	0	0
2	2 ~ 7	0보다 크고 1 이하	1
3	8 ~ 19	1보다 크고 3 이하	3
4	20 ~ 37	3보다 크고 6 이하	6
5	38 ~ 61	6보다 크고 10이하	10

• 즉, 입력 값이 n 이고 출력 값보다 1 작은 값을 t 라고 하면, 6(t^2 + t)/2 >= n-1 이 성립되고 t는 이 부등식을 성립하는 최소값이 될 것 이다. 다음을 이차 방정식의 해를 구하는 방법으로 구해보면

t는 다음을 만족하는 최소값이 될것이고 출력값 = t+1이 된다.

3. 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Integer.parseInt(br.readLine());
        N-=1;
        int pass = (int)Math.ceil((-3+Math.sqrt(9+12*N))/(double)6);
        System.out.println(pass+1);
    }
}