2292 번 : 벌집

문제는 다음과 같습니다.

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

2292번: 벌집

 

풀이 코드는 다음과 같습니다.

#include <iostream>
#include <vector>

using namespace std;
#define ll long long

int main()
{
	ll total{1};
	vector<ll>v;
	v.push_back(total);
	int idx{1};
	while(total<=1000000000)
	{
		total+=(6*idx);
		v.push_back(total);
		idx++;
	}
	ll N;
	cin>>N;
	if(N==1)
		{
			cout<<1<<endl;
		}
	else
	{
		for(int i{1};i<v.size();i++)
		{
			if(v[i]>=N&&v[i-1]<N)
			{
				cout<<i+1<<endl;
				break;
			}
		}
	}
}

범위를 측정하다 보면 육각형의 벌집답게 규칙이 나오는데, 바로 지나가야 하는 방의 개수가 1 늘어날수록 갈 수 있는 방의 개수는 6의 배수로 커진다는 점입니다.

방 1개만 지나가서 갈 수 있는 곳은 1번뿐이고

2개의 경우에는 2~7번 방 , 3개의 경우에는 8~19번 방처럼인데 각각의 방의 개수가 1,6,12로 6의 배수로 커짐을 알 수 있습니다. 이를 이용하여 벡터에 N개 방을 지나서 갈 수 있는 방을 vector에 넣어서 확인할 수 있습니다.

숫자가 1,000,000,000으로 굉장히 크지만 while문을 사용해도 6의 배수로 커지고 while문 안에 더 복잡한 과정이 없으므로 충분히 해결할 수 있는 문제입니다.