[C언어] 백준 2292 : 벌집

백준 2292 : 벌집

 

문제 링크

https://www.acmicpc.net/problem/2292

2292번: 벌집

 

 

문제 내용

(요약) 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 간다고 할 때 몇 개의 방을 지나가는지 계산하는 프로그램을 작성하시오.

ex) 13 → 3개, 58 → 5개

 

 

Idea

최소 방의 개수를 구하라는 문제에 1 → 4 → 13 .... 이런 식으로 접근하면 안 되고,1을 중심으로 주위에 숫자가 몇 개씩 생성되는지를 고려하여 프로그래밍하면 된다.

1부터 생각했을 때, 첫 번째는 1개, 두 번째는 6개, 세 번째는 12개의 방이 생성된다. 즉, n번째의 방의 개수는 6*(n-1) 개다.

 

따라서 이 벌집은 등차수열을 이루며, 이 수열들을 누적하여 N이 어디에 속하는지를 찾아내면 되는 문제이다.

 

 

Code

#include <stdio.h>
 
int main(){
    int N,x=1, cnt=1;
    scanf("%d",&N);
    
    //무한루프
    while(1){
        //N이 누적된 벌집의 수 보다 작거나 같을 경우
        if(N-x<=0) break;
        
        //cnt번째에 생성된 방의 갯수 빼기
        N-=x;
        
        //다음 번째에 생성되는 방의 갯수 계산
          x=cnt*6;
        
        //cnt증가
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}