백준 2292번 벌집

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

위 문제를 보다보니.. 벌집이 생성 될 때 규칙을 찾을 수 있었다.

첫번째 육각형의 최대 값은 1

두번째 육각형의 최대 값은 7

세번째 육각형의 최대 값은 19

네번째 육각형의 최대 값은 37

다섯번째 육각형의 최대 값은 61

즉, 1 7 19 37 61... 순으로 증가하는 셈인데, 여기에 -1을 해주면

0 6 18 36 60 으로 6의 배수가 되는 것을 알 수 있었다.

첫째항은         0 * 6 = 0

두번째항은      1 * 6 = 1

세번째항은      3 * 6 = 18

네번째항은      6 * 6 = 36

다섯번째항은  10 * 6 = 60

이므로, 앞자리 곱셈의 규칙을 찾아내면 되는 것이다.

앞자리의 0 1 3 6 10 의 규칙은 이전 항에서 1 2 3 4 씩 증가되고, 이는 또 이전항에서 1씩 증가하는 등차수열이란 것을 알게되었다.

가만히 생각해보니 고등학교 때 배운 계차수열이 떠올랐다.

물론.. 공식을 아직까지 기억하는 것은 아니지만, 인터넷에서 수열을 찾고, 이를 적용시켰다. 

hexagon[m] 은 m번째 육각형에서 가질 수 있는 최대값을 저장하는 배열이며, 나중에 입력값(n)이 포함되어 있는 m을 정답으로 출력하면 문제를 해결할 수 있다.

#include <iostream>
#define MAX 100001
using namespace std;
int main()
{
    int n, border, result = 0, cnt = 0;
    int hexagon[MAX] = {0, };
    cin >> n;
    
    while (true) {
        border = ((cnt * cnt) + cnt) / 2;
        hexagon[cnt] = (border * 6) + 1;
        
        if (hexagon[cnt] >= n) {
            break;
        }
        cnt++;
    }
    
    for (int i = 1; i < MAX; ++i) {
        if (hexagon[i-1] >= n && hexagon[i] < n) {
            result = i;
            break;
        }
    }
    cout << result << endl;
}