[JS] 백준 2292번 : 벌집

 

Question

백준 2292번 : 벌집

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

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

예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

 

 

2292번: 벌집

 

입력

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

 

출력

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

 

 

입력 예시

13

 

출력 예시

3

 

---

 

 

My Code

 

처음 반복문 안에 if문을 사용했던 코드는 시간이 초과돼서 틀렸다.

let input = require('fs').readFileSync('example.txt').toString().trim().split('\n');
let num = Number(input[0]);

let count = 1;
let sum = 1 ;
while (true) {
    if (num <= (6 * count) + sum ) {
        break;
    }
    sum += 6;
    count++;
}


console.log(count);

틀렸습니다

 

 

 

WHY?

제한시간이 2초 주어진 문제였고 반복문을 계속해서 돌리다 보니 시간 초과가 나와 틀렸다. 역시나 반복문인 아닌 수학적인 접근을 해야했다. 육각형에 여섯 면으로 한 칸씩 옮겨질 때마다 6개, 18개, 36개.... 각 육의 배수가 더해졌음을 알았으나 반복문의 조건을 바꿀 필요가 있었다.

 

 

 

let input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
let num = Number(input[0]);

let count = 1;
let sum = 1 ;
while (sum < num) {
    sum += 6 * count ;
    count++;
}


console.log(count);

맞았습니다!!

 

 

HOW? (풀이방법)

1. 한 칸씩 옮겨질 때마다 늘어나는 도형의 개수의 반복되는 공식을 찾아낸다.

총도형의 개수 : 6개 ➡️ 18개 ➡️ 36개 ➡️ 60개...이다.

+12, +18, +24, +36 순으로 증가했다.

 

2. 총도형의 개수 (sum)와 몇 개의 방(count)을 지나는지 이를 변수로 두고 활용한다.

3. 시작하는 도형이 있기 때문에 sum과 count모두 1로 선언을 해준다.

4. 입력받은 수가 sum보다 클 때까지 while문을 돌린다.

 

 

 

 

수학 공식을 찾아도 대입을 해서 컴퓨터가 알아먹게 잘 설명해야 한다. 자꾸만 익숙한 방법으로 풀려고 한다 🤔

더 쉬운 길이 있으면 돌아가더라도 쉬운 길을 찾아가 보자.