[C/C++] 백준 2292번 C언어

백준 2292번

 

위의 그림과 같이 육각형으로 이루어진 벌집이 있다.

그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다.

 

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오.

 

예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

 

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

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

 

#include <stdio.h>

int main()
{
        int input, result=0, cnt;

        scanf("%d", &input); // 13
        if(input==1){
                printf("1\n");
        }else if(input<=7){
                printf("2\n");
        }else{
                int n=0;
                for(int i=0; result<input; i++){
                        n=n+i;
                        result = 1 + 6 * n;
                        cnt=i;
                }
                printf("%d", cnt+1);
        }
}

 

패턴만 찾으면 쉬운 문제이다.

 

아무 값이나 선택하고 기준점(1)으로부터 선택한 숫자까지의 값들을 쭉 비교해보면 일정한 값을 유지한다는걸 알 수 있다.

 

이를 식으로 풀어쓰면 다음과 같다.

> 1 + 6 * n

 

다시 기준점(1)부터 입력받은 값까지 이동할 때 지나가는 방의 개수를 확인해보면 n과 동일하다는 것도 알 수 있으며 n은 다음과 같이 값이 증가한다.

> n = 0+0

> n = 0+1

> n = 1+2

> n = 3+3 ....

 

위 식에서 좌변 값을 n, 우변 값을 i로 치환하면 쉽게 계산할 수 있다.