백준 2292번 규칙찾기/벌집

[문제보기](https://www.acmicpc.net/problem/2292)

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

예시를 확인하니 출발지는 1로 고정이며 도착지 N이 주어졌을 때, 1에서 N과 같은 둘레에 속해있는 값까지의 거리는 동일하다. 1을 포함했을 때 2~7까지 도착하는 데 필요한 방은 2개, 8~19까지 도착하는 데 필요한 방은 3개, 20~37까지 도착하는 데 필요한 방은 4개이다.

>1, 2, 8, 20, 38...

따라서 이를 그룹으로 묶었을 때, 시작값을 수열로 나타내면 위와 같다. n=1일때 1이고, 2부터는 계차수열이 된다. 6, 12, 18씩 계차가 되므로 수식은 다음과같이 정리할 수 있다.

>A(n+1) = A1+sum(6N) = A1+6n(n+1)/2 = A1+3n(n+1)

따라서 A(n) = 2+3n(n-1)이다. (단, n은 1부터 시작한다.)

여기서 구한 A1은 2로, 두번째 항이다. 따라서 실제 배열의 수식은 다음과 같다.

>A(n)=2+3(n-1)(n-2) (단 n=1일 때는 1이다.)

이제 할 일은 값이 주어졌을 때 n값이 2부터 증가하는 루프문을 돌리면서, 시작값이 주어진 값보다 커졌을 시 n-1값을 출력하고 종료하면 된다. 입력값이 1일때는 1을 출력하고 종료한다. 이를 C로 구현한 코드는 다음과 같다.

```

#include <stdio.h>

int main(){

    int input_data=0, stage=1, start=0;

    scanf("%d", &input_data);

    

    //1이면 1

    if(input_data==1) {

        printf("%d", 1);

        return 0;

    }

    

    //2부터는 2+sum(6(n-1))...

    //따라서 n번째 stage의 값은 2+3(n-2)(n-1)이다. (단, n은 2부터 시작한다.)

    while(1) {

        start = 2+3*(stage-2)*(stage-1);

        if(input_data < start) {

            printf("%d", stage-1);

            return 0;

        }

        

        stage++;

    }

    

    return 0;

}

```

개차수열 공식이 기억나지 않아서 A(n+1)=A1+sum(6N)까지 구해놓고 for문을 돌려야하나하다가, 결국 수식을 검색해서 계산했다. = ㅅ=) 어차피 그렇게 구했더라도 O(n)이었을 것 같긴 하지만...