[C++] 벌집 : 2292번

문제

 

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

---

문제 해석

 

벌집은 1부터 시작하여 시계방향으로 회전하며 1개의 껍질(층)을 생성하며 무한대로 생성된다.

각 껍질(층)의 최대값은 1층부터 { 1, 7, 19, 37, 61 … } 의 값을 가진다.

각 층의 최대값은 { 6, 12, 18, 24 ... } 로 공차가 6인 등차수열을 이룬다.

또한, 각 층에 있는 N 에 도달하기위해 거쳐가는 방 갯수는 N 이 존재하는 층 수와 동일하다.

 

---

풀이

 

#include <iostream>
using namespace std;

int main()
{
	int N; // 찾을 숫자
	long D = 6; // 공차의 공차가 6 인 등차수열
	long currentMax = 1; // 시작 위치로부터 최대값
	long count = 1; // 거쳐가는 방 갯수
	cin >> N;

	while (true)
	{
		if (N == 1) // 1일 때는 무조건 1이 나옴
		{
			cout << 1;
			break;
		}
		currentMax = currentMax + D; // 현재 위치 = 현재위치 + 공차
		D += 6; //. 공차 증가
		count++; // 방 갯수 증가
		if (currentMax >= N) // 현재 숫자가 목적지 N보다 크거나 같으면
		{	
			cout << count; // 방갯수 출력
			break;
		}
		// currentMax = 1, 7, 19, 37, 61
	}
}

 

로직

위에서, 방의 갯수는 현재 층수와 같다고 했다.

따라서, N 까지 도달하는 방의 갯수를 찾기 위해서는 N이 존재하는 층수를 구하면 된다.

각 층의 최대값은 { 1, 7, 19, 37, 61 … } 로 공차가 등차수열을 이룬다.

결론적으로 시작위치인 숫자 '1' 에서 등차수열 { 6, 12, 18, 24 ... } 만큼을 더해가면, 다음 층의 최대값이 나온다.

 

따라서, 찾는 N이 어떤 층의 최대값보다 작거나 같아지는 순간이 목적지에 도달했다는 뜻이다.

 

		currentMax = currentMax + D; // 현재 위치 = 현재위치 + 공차
		D += 6; //. 공차 증가
		count++; // 방 갯수 증가
		if (currentMax >= N) // 현재 숫자가 목적지 N보다 크거나 같으면
		{	
			cout << count; // 방갯수 출력
			break;
		}

반복문을 돌며 공차를 현재 최대값에 계속 더해주고,

공차 또한 6 씩 계속 증가시켜주고,

방 갯수(현재 층 수)를 1씩 증가 시켜주면

현재 최대값과 찾는 N 값을 크기비교 시켜주고

조건을 만족하는 시점에 반복문을 탈출하면 방 갯수를 구할 수 있다.

 

추가적으로, 찾는 N이 1인 경우에는 이 방식대로 하면 답이 2가 나오므로,

1인 경우는 조건문으로 따로 분리하여 준다.

 

		if (N == 1) // 1일 때는 무조건 1이 나옴
		{
			cout << 1;
			break;
		}