52. C++ 백준 2292 번 벌집

안녕하세요! 코딩하는 덕구입니다!

벌집이 형성되는 규칙에 따라 벌집의 위치를 구하는 문제인 C++ 백준 2292 번 입니다~!

문제

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

 

입력

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

출력

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

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

2292번: 벌집

 

#include <iostream>
using namespace std;
int main(){

    int N, cnt = 2, i = 1;
    cin>>N;
    if(N == 1)
        cout<<1;

    else{
        while(N>=cnt){
            cnt +=  i*6;
            i++;
        }
            cout<<i;
    }



//    1 : 1
//    2~7 : 2
//    8~ 19 : 3
//    20~ 37 : 4
//    38~ 61
//    6, 12, 18, 24


    return 0;
}

수학 단원을 들어가면서 이제 코딩 문법보다는 사고력이 중요해진것 같아요 ㅋㅋㅋ

저는 일단 규칙을 먼저 찾았습니다~!

밑에 주석 보이시죠 ㅋㅋㅋ 제가 문제 풀 때 적어놓은 것들인데

: (콜론) 앞 번호는 방 번호이고 뒷 번호는 입력된 벌집 까지의 최소 개수의 방입니다!

1번방은 1개, 2번 방부터는 2개, 8번 방 부터는 3개, 20번 방 부터는 거리가 4개

혹시 여러분들도 보이시나요?

2, 8, 20, 38 

2 + (6*1) = 8

8 + (6*2) = 20

20 + (6*3) = 38

.

.

이제 규칙을 찾았으니 코딩해봅시다!

먼저 예외인 경우입니다! N이 1일때 최소 방의 개수는 1 이므로 1을 출력하는 코드를 작성했습니다!

if(N == 1)
        cout<<1;

 

이후 나머지 case 에 대해서는 방의 범위별 최소 방 개수를 구하기 위해

전 방번호 + i*6 

방번호는 2부터 시작합니다!

2 + 6*1 = 8

8 + 6*2 = 20

이렇게 가겠죠~!

else{
        while(N>=cnt){
            cnt +=  i*6;
            i++;
        }
            cout<<i;

    }

 

2~7번 방은 거리가 2 이고, 8~19 번 방은 거리가 3, 20~ 38번 방은 거리가 4

즉 거리는 i 값과 같죠! 

N이 cnt(다음 거리까지의 방의 범위의 최소값) 일때 반복을 그만두고

i를 출력하면 됩니다~!

예를들어 입력이 13이면 

while(13>= 2){ //첫 번째 반복

cnt = 2 + 1*6

1++;

}

while(13>= 8){ //두 번째 반복

cnt = 8 + 2*6

2++;

}

while(13>= 20){ //세 번째 반복

반복이 돌아가지 않음

}

i 는 3

즉 20보다 작은 13번째 방의 최소거리는 3이 출력됩니다!

이해가 잘 안되신다면 반복을 머리속으로 몇번 돌려보시면 이해가 잘 될겁니다!

C++ 백준 2292 번 이었습니다~! 감사합니다!