백준 알고리즘 / 2292번 벌집

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

 

 

---

 

풀이

 

가운데 1을 시작으로 줄이 바뀔때마다 주변으로 방의 갯수가 늘어나는 구조입니다.

 

N번 줄	포함된 수	N-1번 줄과 차이
1	1
2	2-7	5
3	8-19	11
4	20-37	17
5	38-61	23

정리 해보면 1 -> 6 -> 12 -> 18 -> 24 순서로 6의 배수로 늘어나는것을 볼 수 있고,

고로 해당 줄에 있는 숫자들은 1에게 접근할 수 있는 칸수의 최소값이 같다는 결과가 나옵니다.

 

1번째 줄 -> 1칸

2번째 줄 -> 2칸

3번째 줄 -> 3칸

4번째 줄 -> 4칸

 

 

---

소스 코드 

#include <stdio.h>

int main()
{
	int a, i;
	int b = 1;

	scanf("%d", &a);

	for (i = 1; a > b; i++) {
        /* n번째 줄 마지막 번호보다 크고 n+1 줄 
        마지막 번호보다 작다면 입력값은 n+1 줄에 있다. */
		b += 6 * i; // 6개씩 늘어난다. 
    }
    
    
	printf("%d", i);

}

 

---