[백준] 2292번 : 벌집 C++

시간제한	메모리제한	알고리즘 분류
2 초	128 MB	수학

문제

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

입력

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

출력

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

예제 입력

13

예제 출력

3

---

처음 시도한 코드 (런타임 에러 및 틀렸습니다!)

#include <iostream>
#include <algorithm>
using namespace std;

/* 2292 : 벌집
 * N        R       증감
 * 1        1       0
 * 2 ~ 7    2       6
 * 8 ~ 19   3       12
 * 20 ~ 37  4       18
 * 38 ~ 61  5       24
 * -
 * -
 * 위와 같은 규칙을 찾을 수 있다.
 * 이에 따른 식을 세워보자
 */

void solve() {
    int n;
    cin >> n;
    int end_room = 1;
    int arr[10001] = { 0, 1};

    if(n == 1)
    {
        cout << 1;
        return;
    }
    for(int i=1 ; i <=10000 ; i++)
    {
        arr[i] = end_room;
        end_room = arr[i] + 6*i;
    }
    for(int i=2; i<=10000; i++)
    {
        if(arr[i] >= n && n > arr[i-1]) cout << i;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

배열에 벌집의 한 계층이 끝나는 방 번호를 저장했다.

이 풀이로 진행하면 Out_of_Bound 런타임에러가 뜬다. 

코드를 작성할 때에도, 배열의 범위를 어디까지 잡아야할지 고민했었는데 바르지 못한 풀이였나보다.

 

올바른 접근을 알아내기 위해 다른 자료들을 검색해 찾아보았다.

이 문제를 풀기위해 쉽게 접근하는 방법은 등비 수열을 이용하는 것이다.

벌집의 배치에서 찾아낸 규칙대로, 각 계층마다 증가값이 6이라면 계층을 i, 계층을 지난 후 마지막 방 번호를 sum이라하면 

6*i 의 등비수열의 합을 구하고, 그 합이 n을 넘게되는 i를 찾아 반환하면 답이 나오게 된다.

 

성공 코드

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    
    //예외처리
    if(n == 1)
    {
        cout << 1;
        return;
    }
    
    //방번호 구하기
    int sum = 1;
    int i = 1;
    
    while( n > sum)
    {
        sum += 6*i;
        i++;
    }
    cout << i;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

첫 시도부터 성공까지

깨달은 점은 역시 아직 수학적 접근에 약하다는 점.