[1일 1백준 : 2292번] 벌집

문제

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

 

입력

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

출력

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

 

 

풀이

벌집 모양에 적혀있는 숫자들을 잘 보면 어느 숫자를 계기로 칸이 한씩 더 확장되는 구조를 가지고 있다.

확장되는 숫자들을 나열해보면 1, 7, 19, 37, 61.. 이런식으로 숫자가 나오는데, 이때 이런 숫자들이의 공통된 것들을 찾아보면 6의 배수로 게속 대해져 간다는 것을 알 수 있다.

이를 기반으로 정해진 타겟의 숫자까지의 방의 개수를 알 수 있어진다.

예를 들어서 34번 룸까지 최소 경로로 방을 이동한다고 하면, 34번은 19과 37 사이에 있기 때문에 1, 7, 19, 37을 거치기 때문에 총 4번이 최소 경로가 된다.

마찬가지로  58 개 또한 위와 같게 계산을 하면 최소 경로를 구할 수 있다.

#include <iostream>

/*
1, 6, 12, 18. 24
1, 7, 19, 37, 61
*/
typedef signed long SLONG;
const SLONG RoomCheck(const SLONG N)
{
	SLONG prev = 0, next = 0;
	SLONG maxStep = 1;
	SLONG i = 0;
	if (N == 1)
		return 1;
	for (i = 1; !(prev <= N && N <= next); i++)
	{
		
		maxStep += i * 6;

		next = maxStep;
		prev = maxStep - (i * 6);
	}
	return i;
}

int main(void)
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::ios::sync_with_stdio(false);
	
	SLONG N = 0;

	std::cin >> N;
	std::cout << RoomCheck(N) << "\n";


	return 0;
}

2292번: 벌집 (acmicpc.net)

2292번: 벌집