[백준 알고리즘] 2292번: 벌집 (C)

 

 

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

2292번: 벌집

 

 

---

 

• 문제

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

 

 

---

 

• 입력

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

 

 

---

 

• 출력

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

 

 

---

 

• 예제 입력 1

13

• 예제 출력 1

3

 

 

---

 

• 풀이

#include <stdio.h>
int HoneyComb(int input) {
	int count = 1; //1부터 input의 벌집까지 지나치는 방의 갯수

	while (1) {
		if (input == 1) //1이 입력되면 count를 그대로 출력.
			break;
		else if (input > 0) { //input이 0보다 크면 count를 증가하고 6n만큼 빼기.
			input -= 6 * count;
			count++;
		}
		else //input이 0과 같거나 보다 작아지면 누적된 count를 출력.
			break;
	}
	return count;
}
int main(void) {
	int input; 
	scanf_s("%d", &input);

	printf("%d", HoneyComb(input));
	return 0;
}

벌집을 한 칸 이동할 때마다 1, 7, 19, 37, 61... 6의 배수만큼 늘어나는 것을 알 수 있다.

 

이런 패턴을 활용해서 입력 받은 input 값에 6의 배수만큼 계속 뺄셈을 해준다면 지나치는 방의 갯수를 알 수 있다.

 

input이 0보다 크다면(벌집의 외곽을 다 돌고나서도 값이 남아있다면) count를 늘려주고 input 값에 6의 배수를 뺄셈해준다.

 

 

예를 들어서 58이 input 값으로 주어졌다면,

int count = 1

input = 58 - 6 * 1
count++ // count == 2

input = 52 - 6 * 2
count++ // count == 3

input = 40 - 6 * 3
count++ // count == 4

input = 22 - 6 * 4
count++ // count == 5

 

input이 마지막에 0보다 작아지기 때문에 반복문을 탈출하고 방을 지나친 갯수인 count 변수를 출력해주면 된다.