백준 2292번 벌집 풀이

육각형의 벌집에서 번호를 매기고 1번 방부터 그 번호로 가는데 거쳐야 하는 방의 최소 개수를 구하는 문제.

 

풀이

일단 기본적으로 이동한 방의 개수는 1개부터 시작이다. 그 이유는 1번부터 시작이기에 이미 방을 1개 거쳤기 때문. 예제를 잃어보면 1번방을 지나간 방으로 친다는걸 알 수 있다.

 

n개의 방을 이동했을때 갈 수 있는 방을 정리해보았더니

 

n=1.   1   1개. 

n=2. 2,3,4,5,6,7.  6개 

n=3  8,9,10,11,12,13,14,15,16,17,18,19. 12개

n=4. 20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37.  18개

n=5. 38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61  24 개

.

.

.

 

같이 나왔다. 어떤 규칙성이 보이지 않는가? n개의 방을 이동했을때 이동 할 수 있는 방의 개수는 (n-1)*6이란걸 알 수 있다.(1은 제외).

그러면 특정방까지의 최소 경로는 어떻게 알아내는가?

n단계에서의 최소인 수와 최대의 수 사이에 알아내려는 방 번호가 있다면 그 단계가 최소경로일 것이다.

import java.util.Scanner;

public class Main {
	public static long calculate(long n) {
		int floor=1;
		int countFloor=1;
		long max=1,min=1;
		while(true) {
			if(n==1)
				return 1;
			else {
				min=countFloor+min;
				countFloor=floor*6;
				max=min+countFloor-1;
				if(n>=min && n<=max) {
					return floor+1;
				}
				else {
					floor++;
				}
			}
		}
		
	}
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		long n;
		n=scanner.nextLong();
		int answer=(int) calculate(n);
		System.out.println(answer);
	}
}