[C언어] Backjoon_Code 2292, 벌집

| 문제

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

 

| 입력

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

 

| 출력

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

 

| 예제 입력 1

13

 

| 예제 출력 1

3

 

| 문제의 키 포인트

1. 규칙을 발견하자.

2. 6각형에서 뻗어나가는 방향은 총 6가지이다. 그러므로 경우의 수는 6가지

(1) 1 > 2 > 9 > 22 > 41 > 66... ( 1 | 7 | 13 | 19 | 25...)

(2) 1 > 3 > 11 > 25 > 45... ( 2 | 8 | 14 | 20...)

(3) 1 > 4 > 13 > 28 > 49... ( 3 | 9 | 15 | 21...)

(4) 1 > 5 > 15 > 31 > 53... ( 4 | 10 | 16 | 22...)

(5) 1 > 6 > 17 > 34 > 57... ( 5 | 11 | 17 | 23...) 

(6) 1 > 7 > 19 > 37 > 61... ( 6 | 12 | 18 | 24...)

각 수들은 ()와 같이 증가하고 있으며, 해당 값은 6씩 증가하는 특징을 보여준다.

 

이를 수학적으로 정리하면,

증가하는 숫자는 공차 6의 등차수열을 이루고 있으므로

등차수열의 일반항: a_n= a₁ + (n - 1)d

(1) 첫 항: 1, 공차: 6 , a_n= 1 + (n - 1)6 = 6n - 5

(2) 첫 항: 2, 공차: 6 , a_n= 2 + (n - 1)6 = 6n - 4

(3) 첫 항: 3, 공차: 6 , a_n= 3 + (n - 1)6 = 6n - 3

(4) 첫 항: 4, 공차: 6 , a_n= 4 + (n - 1)6 = 6n - 2

(5) 첫 항: 5, 공차: 6 , a_n= 5 + (n - 1)6 = 6n - 1

(6) 첫 항: 6, 공차: 6 , a_n= 6 + (n - 1)6 = 6n

 

이제 육각형 안의 값을 각각의 공차로 식을 정리하면,

(1) 첫 항: 1, 공차: 6n - 5, a_n= 1 + (n - 1)(6n - 5) = 6n² - 11n + 6

(2) 첫 항: 1, 공차: 6n - 4, a_n= 1 + (n - 1)(6n - 4) = 6n² - 10n + 5

(3) 첫 항: 1, 공차: 6n - 3, a_n= 1 + (n - 1)(6n - 3) = 6n² - 9n + 4

(4) 첫 항: 1, 공차: 6n - 2, a_n= 1 + (n - 1)(6n - 2) = 6n² - 8n + 3

(5) 첫 항: 1, 공차: 6n - 1, a_n= 1 + (n - 1)(6n - 1) = 6n² - 7n + 2

(6) 첫 항: 1, 공차: 6n, a_n= 1 + (n - 1)(6n) = 6n² - 6n + 1

 

3. 2번에 경우의 수에 더불어 해당 대각선에 인접한 숫자도 고려해야 한다.

ex. 58

 

4. 원 별로 숫자의 개수의 특징을 파악하자.

(1) 노란 육각형: 6개  | 2, 3, 4, 5, 6, 7

(2) 초록 육각형: 12개 | 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

(3) 파랑 육각형: 18개 | 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37

....

이를 통해 각 육각형에 배치되는 숫자가 6개씩 증가하는 특징을 볼 수 있다.

(1) 노란 육각형의 경우, 최소 2개의 방

(2) 초록 육각형의 경우, 최소 3개의 방

(3) 파랑 육각형의 경우, 최소 4개의 방

....

이라는 공통점을 지닌다.

 

위 범위를 수학적으로 정리하면

(1) 2 ≤ N ≤ 7

(2) 8 ≤ N ≤ 19

(3) 20 ≤ N ≤ 37

....

앞의 숫자의 공차는 3n, 뒤의 숫자의 공차는 3(n+2)라는 것을 알 수 있다.

이를 등차수열의 일반항으로 일반화시키면

2+(n-1)3n ≤ N ≤ 7 +(n-1)3(n+2)

식을 정리하면,

3n² - 3n + 2 ≤ N ≤ 3n² + 3n + 1

 

| 해결방안(Solution)

1. 위와 같이 각 범위의 표준식을 구했으므로, 반복문을 통해 각 범위별 값을 출력한다.

단, 여기서 n은 1부터라는 점.

 

| 소스코드(SourceCode)

// BOJ_2292_벌집(Honeycomb)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int main(void)
{
	int i = 1, N; 
	int cnt = 1;
    
    // 입력부
	scanf("%d", &N);
	
	if (N == 1)
	{
		printf("%d", 1);
		return 0;
	}

	while (1)
	{
		if (N >= (3*(pow(i,2)) - 3*i + 2)  && N <= (3*(pow(i,2)) + 3*i + 1))
		{
			printf("%d", cnt + 1);
			break;
		}
		else
		{
			i++;
			cnt++;
		}
	}

	return 0;
}

2가지 방향으로 규칙을 도출했는데, 첫번째의 경우 해당 방향을 제외한 다른 방향에 대한 숫자에 대해서는 값을 출력할 수 없어서 두번째 규칙으로 코드를 작성하였습니다. 고등학교 때 기본적으로 배우는 등차수열을 활용하여 문제 풀이를 진행하였으며, 위 풀이과정을 보시면 이해하시기 쉬울 것입니다.

 

그럼 오늘도 즐거운 코딩!

 

| 문제 출처

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

2292번: 벌집