[C] 백준 | 2292번 코드 - *벌집

> 문제

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

> 핵심

등차수열적으로 껍데기 쌓으면서 범위 파악하기

> 해결방안

한시간동안 끙끙 고민하다가 결국 구글링으로 남의 코드를 슬쩍 봤다...

​

나는 어떻게 최단경로를 도출해 내야하는지, 재귀함수를 써야하는건 아닌지 복잡하게 생각하고 있었는데

전혀 그런 방식으로 푸는 문제가 아니었다.

​

벌집은 육각형 구조로 껍질이 한겹 한겹 쌓일수록 방의 개수가 등차수열으로 증가한다(?)

​

1번방 | 2 ~ 7번 방 (6개) | 8 ~ 19번 방 (12개) | 20 ~ 37번 방 (18개) | 38 ~ n번 방 (6 * cnt개)

​

cnt = 1부터 하나씩 늘려가면서(껍질을 하나씩 쌓아가면서)

해당 범위 내에 찾고자 하는 방이 존재하는지만 확인하면 된다.

방이 어느 위치에 있는지에 대한 방향성은 이 문제에서 전혀! 고려할 대상이 아니라는 것이다..

​

어느 방향으로 가고 어디서 꺾고 이런건 아무 쓸데도 없다..

그것도 모르고 한시간동안 1-> 2-> 9 -> ... 이런거나 따지고 앉아있었다. 어휴.

​

아무튼. 껍질 중 최솟값 2 - 8 - 20 - 38 - ... - 을 기준으로 N값이 껍질 범위에 들어오면

반복문을 탈출하고 현재 cnt값만 출력하면 되는거였다.

 

> 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int N, cnt = 0, num = 2, i;

	scanf("%d", &N);
	
	while (1)
	{
		num = num + (cnt * 6);
		if (N < num)
			break;
		cnt += 1;

	}
	printf("%d\n", cnt + 1);

	return 0;
}