[백준 2292] 벌집

[백준 2292] 벌집

문제 출처 : https://www.acmicpc.net/problem/2292

---

문제

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

입력

---

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

출력

---

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

예제 입력

13

예제 출력

3

• 문제 이해하기

벌집모형의 사진을 보면, 가운데 1을 기준으로 이웃하는 방을 거쳐 계속 증가하는 모습을 볼 수 있다. (숫자가 1씩 증가하는 위치의 벌집으로 쭉 따라가보면 어떤 식으로 나아가는지 알 수 있을 것이다.)

우리가 어떤 숫자를 주었을 때, 이 숫자가 들어있는 방이 중앙 1번 방에서 최소 몇개의 방을 지나서 갈 수 있는지 구하는 문제다. 이때 1번 방과 마지막 N번 방의 수를 포함해서 최소 개수를 구해야 한다.

• 계획 및 문제해결

우선, 최소 개수가 1개, 2개, 3개인 숫자들에서 규칙을 찾아야 한다고 생각했다. 

최소 개수가 1인 수는 1밖에 없고, 2인 수는 2~7, 3인 수는 8~19였다. 

이 구간마다 증가하는 규칙이 존재한다면, N을 입력했을 때 해당 구간에 위치한 최소 개수를 출력하면 된다.

중앙 1을 기준으로 둘러싸는 방의 수는 6, 12, 18, 24로 증가하고 있었다.

최소 개수에 해당하는 변수 count, 그 해당 최소 개수에 둘러싼 방의 수 중에서 가장 큰 수를 변수 number를 만들어 활용하자.

int N; // 입력할 수
int number = 1;
int count = 1;
 
cin >> N; // N 입력 

시작을 중앙 1번 방으로 잡을 때, number = 1이고 최소 개수인 count = 1이기 때문에 미리 초기값을 설정해준다.

이제 while문을 활용해서 입력한 N 값이 number보다 큰 동안 다음과 같이 number와 count를 증가시켜 나가면 된다.

while (number < N) {
    number += count * 6;
    count++;
}

계속 while문이 진행되다가, number가 N보다 커지는 순간이 올 것이다. 이때 해당하는 count 값이 N이 중앙 1에서부터의 지나는 최소 개수의 방이 된다.

• 전체 소스 코드

#include <iostream>
 
using namespace std;
 
int main(void) {
 
    int N; // 입력할 수
    int number = 1;
    int count = 1;
 
    cin >> N;
 
    while (number < N) {
        number += count * 6;
        count++;
    }
 
    cout << count;
}