[백준 2292] 벌집

백준 2292번 - 벌집

백준 2292번

❓ 문제

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

---

✏️ 풀이

수학 문제다.
처음엔 뭔가 느낌이 BFS나 DFS처럼 탐색인가? 생각했는데, 아니었다.
이 문제의 규칙만 잘 알아낸다면 쉽게 풀 수 있는 문제였다.
먼저 아래 그림을 보자.

빨간 영역이 각 방의 마지막 번호이다.
input이 1이면 output은 1,
input이 2~7이면 output은 2,
input이 8~19이면 output은 3,
input이 20~37이면 output은 4….

이런식으로 흘러간다.

따라서 저 숫자의 규칙만 찾아낸다면 되겠다.

규칙은 이러하다.  
방의 갯수가 늘어남에 따라 An = An-1 + 6(n-1) 이라는 공식이 세워진다.  
  +6   +12   +18   +24
1    7    19    37    61

위와 같은 규칙을 찾았으니, 코드로 표현하면 된다.
아래는 정답 코드이다.

---

✔️ 정답 코드

#include <iostream>
#include <string>
#define LL long long int

using namespace std;

int solve(int N);

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	int result = solve(N);
	cout << result;

	return 0;
}

int solve(int N) {
	LL num=1;
	int result = 2, count=1;

	if (N == 1)
		return 1;

	while (1) {
		if (N <= num + (6*count))
			break;
		else {
			result++;
			num = num + (6*count++);
		}
	}
	return result;
}