[BOJ] 백준 2292 벌집-java

문제

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

입력

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

출력

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

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

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int num=in.nextInt();
        int room=1,tmp=1;
        for(int i=1; i<100000; i++) {
            if(tmp<num && (tmp+=6*i)>=num) {
                room +=i;
                break;
            }
        }
        System.out.print(room);
    }
}

 

풀이

벌집에서 입력받은 수가 몇개의 방을 지나야 하는지 알기 위해서 규칙을 찾아야 합니다.

숫자가 몇개의 방을 지나는지 알아보기 위해서 각 숫자가 지나는 방의 개수를 나열해봅니다. 

1개의 방을 지나는 수 : 1 (1개)

2개의 방을 지나는 수 : 2~7 (6개)

3개의 방을 지나는 수 : 8~19 (12개)

4개의 방을 지나는 수 : 20~37 (18개)

5개의 방을 지나는 수 : 38~61 (24개)

이런식으로 각 범위에 해당하는 최대수를 나열하면 등차가 6의 배수인 계차수열 형태로 나옵니다.

각 범위의 최대 수를 기준으로 나열해보면 1, 7, 19, 37, 61... 인데 이것은 1, 1+6*1, 7+6*2, 19+6*3, 37+6*4 로 나타낼 수 있습니다.

a(n)=a(n-1)+6*(n-1)이라는 식을 얻을 수 있으므로 tmp라는 변수에 각 범위의 최대수를 넣어서 그 최대수와 이전항(이전범위 최대수) 사이에 속하는 수라면 n을 출력해주고 그것이 방의 개수가 됩니다.