[백준/C언어] 2292번 - 벌집

백준 웹사이트 "2292번 - 벌집" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

 

---

문제

2292번: 벌집

---

소스 코드

#include <stdio.h>

int main(void){
	int N; //N의 최댓값 10억은 int 범위 내
	scanf("%d", &N);

	/*	
    		1: 1개
		2~7 (1+1 ~ 1+6): 2개
		8~19 (1+6+1 ~ 1+6+6*2): 3개
		20~37 (1+6+6*2+1 ~ 1+6+6*2+6*3): 4개
		38~61 (1+6+6*2+6*3+1 ~ 1+6+6*2+6*3+6*4): 5개
		...
		1+6+6+2+...+6*n+1 ~ 1+6+6+2+...+6*n+6*(n+1): n+2개 (n>=0)
	*/
	
	if(N==1){
		printf("1");
	}
	else{
		int n=0;
		/*
			1+6+6+2+...+6*n+1 = 2 + 3*n*(n+1)
			1+6+6+2+...+6*n+6*(n+1) = 1 + 3*(n+1)*(n+2)
		*/
		while(1){
			if(2+3*n*(n+1)<=N && N<=1+3*(n+1)*(n+2)){ // N의 범위 찾기
				break;
			}
			n++;
		}
		printf("%d", n+2);
	}
}

---

문제 풀이

  육각형 모양의 벌집 위에서 중앙을 기준으로 규칙적으로 번호를 매기고 있기 때문에, 분명 어떠한 규칙은 존재합니다. 이를 알아내기 위해 아래 그림과 같이 분석을 해보았는데, 1을 기준으로 한 바퀴를 돌기 위해 필요한 숫자의 개수는 일정하게 늘어납니다. 첫 바퀴에는 6개의 숫자가 필요하고, 두 번째에는 12개, 세 번째에는 18개가 필요한 식으로, 6개씩 증가하죠?

이러한 규칙을 수식으로 표현하면, 아래와 같이 됩니다.

1: 1개
2~7 (1+1 ~ 1+6): 2개
8~19 (1+6+1 ~ 1+6+6*2): 3개
20~37 (1+6+6*2+1 ~ 1+6+6*2+6*3): 4개
38~61 (1+6+6*2+6*3+1 ~ 1+6+6*2+6*3+6*4): 5개

---

1+6+6+2+...+6*n+1 ~ 1+6+6+2+...+6*n+6*(n+1): n+2개 (n≥0)

1번째 바퀴의 마지막 숫자는 1+6, 2번째 바퀴의 마지막 숫자는 1+6+6*2인 식이죠? 따라서 n번째 바퀴의 첫번째 숫자는 1+6+...+6*(n-1)+1이 되고, 마지막 숫자는 1+6+...+6*n이 됩니다.

  여기까지 규칙을 알아냈으면, 이제 N이 어느 범위에 속하는지만 구하면 됩니다. Line 26의 while문을 통해 N이 속해있는 범위를 구할 때까지 n을 계속해서 증가시킵니다. 그러다가 Line 27의 조건을 만족하는 n에 도달하면 while문을 빠져나오고, n+2를 출력합니다. 전체적으로 어려운 코드는 아니지만, 규칙을 구하는 과정이 조금 까다로운 문제였습니다.