[JS] 백준 2292번 벌집

 

출처

백준 온라인 저지

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

2292번: 벌집

 

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다.

 

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오.

 

예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

풀이

해당 문제는 규칙 없이 단순 반복문을 돌릴 시 시간 초과가 나는 문제입니다.

 

규칙을 찾아보니 범위가 증가할 때마다 둘러싼 방이 각 6, 12, 18, 24 씩 (6n) 증가하고 있습니다.

 

단순하게 생각하면,

2 ~ 7번까지는 2번 만에 이동이 가능하며

8 ~ 19까지는 3번 만에 이동이 가능합니다.

 

범위는 1에서 증가하는 방만큼 계속 누적시켜 주며 1, 7(6), 19(12), 37(18)

 

범위에 따른 블록 합이 입력받은 N보다 작을 때까지 반복해주면 됩니다.

 

시작하는 범위는 1에서 시작하며 시작 블록 값도 "1" 한 개의 블록이므로 1이 될 것입니다.

 

코드

const input = require('fs').readFileSync('/dev/stdin');

let range = 1, block = 1;

while (block < input) {    
  block += 6 * range;

  range++;
}

console.log(range);