백준_2292_벌집

 

 

 

문제 풀기 전 생각)

연속되는 숫자가 원형을 그리며 시계방향으로 회전하고 있으므로 규칙을 찾아 문제를 풀어야겠다는 생각을 했습니다.

1을 기준으로 직선을 그어보면,

1->5->15->31->53  (+4, +10, +16, +22)

1->7->19->37->61  (+6, +12, +18, +24)

보다시피 커지는 숫자가 6씩 증가하고 있습니다.

 

위 규칙을 이용해서, 입력받은 숫자에서 -6, -12, -18 .... 을 하며 몇 번 연산되었는지 세어보면 몇 번째 궤도에 위치해 있는지 구할 수 있을 것 같습니다. 

 

 

풀이)

N을 입력받아 규칙이 몇 번 사용되었는지를 확인하도록 프로그래밍합니다. 

궤도가 올라갈수록 가장 작은 값과 가장 큰 값의 차이가 커지므로 이를 해결할 수 있도록 공식을 세웁니다.

 

1.규칙이 몇 번 사용되었는지 계산하는 반복문을 작성합니다.

같은 궤도 상에서 가장 큰 수는 규칙이 한번 더 사용되고 1이 남는다는 공통적인 성질이 있으므로, 

아래의 if문에 있는 조건을 사용하면 이를 해결할 수 있습니다.

int i = 0;
int count = 0; // 규칙이 몇 번 사용되었는지 셀 변수
while (1)
{
    N -= (6 * i);
    i++;
    count++;

    if (N <= (6 * i) + 1)
        break;
}

 

 

2. 처음에는 반례를 생각하지 않은 채 저대로 제출했지만, 틀렸다는 답을 받았습니다.

생각해보니 위 반복문대로라면 1을 입력했을 떄 2가 출력되기 때문에 조건을 추가하였습니다.

if (N == 1)
{
    printf("1\n");
    return 0;
}

 

 

3. 마지막으로, 이 문제는 시작하는 방과 끝 방을 포함해야 하기 때문에 출력할 때 count+1 을 출력하도록 하였습니다.

 

전체 코드)

#include <stdio.h>

int main(void)
{
    int N = 0;
    scanf("%d", &N);

    if (N == 1)
    {
        printf("1\n");
        return 0;
    }

    int i = 0;
    int count = 0; // 규칙이 몇 번 사용되었는지 셀 변수
    while (1)
    {
        N -= (6 * i);
        i++;
        count++;

        if (N <= (6 * i) + 1)
            break;
    }

    printf("%d\n", count + 1); // 규칙이 사용된 횟수 +1 출력

    return 0;
}

 

 

규칙에 6이라는 숫자를 이용해야 한다는 것은 찾기 쉬웠지만, 같은 궤도 위에 위치한 가장 큰 숫자가 가지는 공통적인 특징을 찾는데 시간이 좀 걸렸습니다.

 

처음에는 범위 규칙을 정해서 반복문을 쓸까도 생각해보았지만, N이 십억 이하의 자연수라 너무 오래 걸릴 것 같아 위의 방식으로 풀었습니다.