[백준 알고리즘] 2292번 - 벌집

1. 문제 및 예시 실행결과

 

 수학 카테고리에서 문제를 풀기 전 문자열 카테고리와는 다른 종류의 겁이 들었던 기억이 난다. 코딩을 잘 한다는 것이 아직도 뭔지 모르겠다. 문법을 잘 알고, 에러를 만들지 않는 사람도 있고 수학적 기교로 코드수를 줄이거나 알고리즘을 잘 설계하는 사람이 있을 것이다. 전자와 후자 전부 대단하지만, 나는 이 모든 부류를 공부할 때 겁을 먹는 것 같다. 언젠가는 이런 겁도 안먹기를 바란다.

 

 이번 문제는 규칙을 파악하는 것이 매우 중요한 문제이다.(모든 코딩문제가 그런 것 같지만......) 실제로 나는 이 문제를 위해 그림도 그렸다 ㅠㅠ 다음은 문제와 예시 실행결과이다.

 

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

2292번: 벌집

---

2292번

---

 문제가 복잡하고 그림이 이해 안될 수 있겠지만, 규칙을 찾아 일반화한다면 쉽게 해결할 수 있다. 다음은 예시 실행결과이다.

---

2292번 예시 실행결과

---

 이미 알 수 있겠지만, 이 문제는 최단 거리보다는 입력된 수가 몇층에 있는지를 파악하는 문제이다. 6각형은 어떤 층이던 그 층수만큼만 움직이면 되기 때문에 최단거리는 상관이 없기 때문이다. 다음은 문제 풀이이다.

 

2. 풀이 과정

 

 여러가지 규칙이 있겠지만, 저는 도형의 관점으로 규칙을 찾았다. 홈페이지의 그림은 개인적으로 보기에는 조금 어려워 직접 그림을 그려보았다.

---

---

 그림을 보면 알겠지만 벌집 도형은 층으로 나눌 수 있다. 그리고 나는 이 층으로 문제를 풀었습니다. 이유는 해당 숫자가 몇층에 있는지를 알면, 최단거리는 결국 그 층까지의 거리이기 때문이다. 빨간색 태두리는 1층이고, 보라색은 2층 주황색은 3층이라고 생각하면 될 것 같다. 수학을 잘 하는 사람들은 6의 배수로 늘어난다는 규칙을 바로 찾을 수 있었겠지만 필자는 공부를 그렇게 잘 하지 못해 몸으로 때웟다 ㅠㅠ. 나는 일단 중심이 되는 축을 그렸다. 중심은 가장 가운데 즉, 1이 적혀져있는 블럭이고 각 면에 수직으로 만나는 면들을 선으로 이었다. 다음과 같은 그림이 될 것이다.

---

---

 이제 기준선을 보고, 층을 살펴보도록 하자. 기준선에 해당하는 블럭(편하게 정육면체를 블럭이라고 부르겠습니다.) 사이에 몇개의 블럭이 있는지를 파악하면 규칙이 보인다. 보라색은 2층에 해당하는 블럭이고, 기준선에 포함되지 않은 블럭을 파란색으로 색칠해보겠다. 그럼 다음과 같은 그림이 나올것이다.

---

---

 파란색 블럭이 하나씩 사이사이에 끼워져있는 모습이다. 그럼 3층을 보자. 3층에 속하면서 기준선에 포함되지 않는 블럭을 파악해보면 다음과 같은 그림을 그릴 수 있다.

---

---

 초록색으로 표시된 블럭의 갯수는 2개이다. 이제 규칙이 완성된것 같다. 층이 늘어날 때마다 기준선에 해당하지 않는 블럭은 한개씩 늘어나고, 그런 블럭들이 6묶음 있으므로 다음과 같은 공식이 완성된다.

---

층에 존재하는 블럭의 갯수 = 6 + (해당 층수 - 1 * 6) 

---

 위의 일반 식으로 코드를 작성하면 다음과 같을 것이다.

 

#include <stdio.h>

int main(void) {
	int input;
	scanf("%d", &input);
	
	if (input == 1)
		printf("%d", 1);
	else {
		int i = 1;
		int num = 0;

		while (1) {
			num += 6 + ((i - 1) * 6);
			if (input <= num + 1)
				break;
			i++;
		}
		printf("%d", i + 1);
	}
	return 0;
}

 

3. 결어

 

 항상 말하지만 이게 정답은 절대 아니다 ㅠㅠ(훨씬 짧은 코드로 해결하는 분들이 많을 것이다.) 또 어렵거나(개인적으로) 풀이과정이 특이한 문제가 있으면 이 카테고리에 게시할 것이다.