[java] 2292 벌집

문제

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

입력

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

출력

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

 

package backjoon_2292;
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
//        int[] arr = null;
//        bulzip(n);
        System.out.println(bulzip(n));
    }
    
    public static int bulzip(int n) {
        int[] arr = new int[n+1];
        int res = 1;
        for(int i =1; i<=n; i++) {
            arr[i] = res;
            if(i%6==0)
                res++;
        }
        return arr[n];
    }
}
 

 

 

배열을 써서 그런지 메모리 초과가 나왔다.

 

이 문제는 현재층 = (6*(이전까지 탐색했던 층 개수)+ 이전 층 높이 ) 로 임을 생각하면 쉽게 풀 수 있다. 나는 배열로 짜다가 생각이 엉켜버려서 시간이 걸렸다. 

 

그래서 로직을 바꿔야했다. 일단 함수에서는

while(true) {
	max += 6*res;
	res++;
			
	if(n <= max)
		break;
}

을 넣었다.

max는 지금 최대층을 말하고 n이 입력받은 수라 입력받은 수에 도달하면 멈추게 만들었다. res는 현재 층을 계산한다. 

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        System.out.println(bulzip(n));
    }
    
    public static int bulzip(int n) {
        if(n == 1)
            return 1;
        
        int res = 1;
        int max = 1;
        while(true) {
            max += 6*res;
            res++;
            
            if(n <= max)
                break;
        }
        
        return res;
    }
}
 

 

1층일 경우에만 1을 리턴하고 고정시켜둔다. 그리고 while에서 현재층 = (6*(이전까지 탐색했던 층 개수)+ 이전 층 높이 ) 을 쓰기 위해 max를 쓰는데 max는 우리가 도달해야하는 입력받은 현재 최고 높이(그러니깐 현재층을 탐색하기 위해 씀)을 의미한다. res는 탐색중인 층의 높이를 의미한다고 볼 수 있다.