백준(BAEKJOON): 벌집(2292번)

Source

문제

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

입력

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

출력

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

예제 입력 1

13

예제 출력 1

3

해설

수학을 모르는 사람으로선 참 어려운 문제다. 여러 방식으로 수의 성질을 찾아 고심하던 중 {1, 7, 19, 37, 61 ...} 수열에 집중하게 되었다. 이 그림을 양파라고 한다면 같은 껍질에 있는 수의 범위를 알 수 있는 수들이다. 즉 2~7이 하나의 껍질을 이루고 8~19가 또 다른 껍질을 이루는 식이다. 각 껍집의 수는 1에서 해당 수까지의 최단 거리에 대응한다.

결국 수열 {1, 7, 19, 37, 61 ...}을 적절하게 코드로 구현하면 되는 문제이다.

이 수열의 원소들은 1에서 각각 6, 12, 18, 24씩 증가하고 있다. 이는 곧 6*1, 6*2, 6*3 ...로 나타낼 수 있다. 이전 수에서 6*n(n >= 1)이다. 이를 간단한 수식으로 나타낼 수 없을까 하여 종이를 펴고 이래저래 수식을 써봤지만 시간만 흐르고, 그 시간만큼 내 정신도 흐려질 뿐이었다. 결국 간단한 수식을 고안해 내지 못한 채 아래와 같이 코딩하였다.

이미 졸음으로 멍해진 탓에 깔끔한 코딩을 생각할 겨를 없이 마구잡이 코딩이다. 수열에서 이전 수를 만들기 위해서 prev를 선언하고 1로 초기화 하였다. 그리고 껍질 수를 저장하기 위해 count도 1로 선언하였다. 다음 수는 prev + 6 * i(i >= 0)으로 하였다. 입력받은 수 input_num이 1이면 바로 for문을 빠져나와서 count를 출력한다.

소스코드:C

#include <stdio.h>
int main(int argc, char *argv[])
{
    int input_num, i = 0;
    int count= 1, prev = 1;

    scanf("%d", &input_num);

    while(1) {
        if (input_num == 1) {
            break;
        } else if (input_num > prev + 6 * i) {
            count++;
            prev = prev + 6 * i;
        } else {
            break;
        }
        i++;
    }

    printf("%d\n", count);
    return 0;
}