[Baekjoon] 2292번: 벌집

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

2292번: 벌집

 

이번 문제를 보고서는 규칙을 금방 찾아낸 사람에게는 아주 쉬운 문제이지만 규칙을 잘 발견하지 못한 사람에게는 엄청나게 어려운 문제가 될 수도 있을 것 같다는 생각이 들었다(물론 전혀 아닐 수도 있다 ㅎㅎ 반박 시에는 항상 제가 죄송합니다).

 

---

 

문제 해결 과정

착안

아래의 그림과 같이 구획을 나누어 규칙성에 따라 문제를 해결한다.

벌집의 중앙 1에서 \(N\)번 방까지 최소 개수의 방을 지나서 갈 때 지나는 방의 개수를 \(k\)라고 하면, 그림과 같이 \(k\)의 값이 같은 방끼리 그룹화했을 때, 그 그룹은 항상 육각형 모양을 이루게 된다(\(k = 1\)인 경우 제외). 따라서 \(k = n\)을 만족하는 방의 수가 \(6(n-1)\) 개라는 규칙성을 확인할 수 있다.

 

구현

위의 규칙에 의하여 \(k ≤ n\)을 만족하는 방의 개수는 \(1 + 6 + 12 + ... + 6(n-1)\) 이므로, \(k = n\)을 만족하는 방 중에서 가장 마지막 번호가 \(1 + 6 + 12 + ... + 6(n-1)\) 임을 확인할 수 있다. 따라서 반복문에서 매 loop마다 6의 배수씩 더해가며 \(n\)보다 처음 커지는 end의 값을 찾았을 때, 반복문을 돈 횟수 + 1을 출력하면 된다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;

	int end = 1, i = 1;
	while (n > end)
		end += (6 * i++);
	
	cout << i;

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.