백준 2292번

CharliePark·2020년 9월 29일
0

TIL

목록 보기
53/67

BOJ 2292 : 벌집

벌집의 가장 중앙의 1번방에서 멀어지는 거리에 따라, 1번 레이어(1번 방), 2번 레이어 (2~7번 방) 과 같은 식으로 구분하면

이웃하는 방으로 갈 때 최소로 방을 지나는 개수는 곧 그 방이 몇 번째 레이어인지와 같다

1번 레이어를 제외하고, 레이어가 늘어날 때 마다 한 개의 레이어에 속하는 방의 개수가 6개씩 늘어난다.

이때 어떤 숫자가 어느 레이어에 속하는지 알기 위해서, 각 레이어에서 가장 큰 숫자를 확인하면 된다.

3번 레이어의 가장 큰 숫자보다 어떤 숫자가 크고, 4번 레이어의 가장 큰 숫자보다 어떤 숫자가 같거나 작다면 그 숫자는 4번 레이어에 속함을 알 수 있다.

어떤 레이어의 가장 큰 숫자를 알기 위해서는, 이전 레이어부터 어떤 레이어까지의 방 개수를 모두 더하면 된다

레이어의 방 개수는 1, 6, 12, 18, 24 와 같은 식으로 증가하므로

2번 레이어 이후부터는 공차가 6인 등차 수열의 합으로 구하고, 1번 레이어의 방 개수인 1을 더해주면 된다.


#include <stdio.h>

int main()
{
    int N;
    int num = 0;

    while (scanf("%d", &N) != 1) continue;

    while (1)
    {
        int temp = 1 + 6 * num * (num + 1) / 2;
        if (temp >= N)
            break;
        num++;
    }

    num++;

    printf("%d", num);
    return 0;
}

0개의 댓글