[BOJ-2292][C++] 벌집 ✨

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

13

 

예제 출력 1 

3

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2004 B번

• 문제의 오타를 찾은 사람: waylight3

 

알고리즘 분류

• 수학

 

문제 출처

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

2292번: 벌집

 

---

 

문제 해결 방법

어렵게 풀었던 문제였다.

우선 그림에서 규칙을 찾아보았다.

 

 

찾은 규칙을 표에 정리하였다.

 

계층	요소	요소 개수	지나가는 방 개수
1	{ 1 }	1	1
2	{ 2, 3, 4, 5, 6, 7 }	6	2
3	{ 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }	12	3
4	{ 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 }	18	4
5	{ 38, 39, 40, 41, 42, ..., 61 }	24	5
...	...	...

 

계층이 1개 씩 증가할 수록 요소의 개수가 6개씩 증가함을 확인할 수 있었다. 또한, 지나가는 방 개수 또한 1개씩 증가함을 확인할 수 있었다.

 

우선, 각 계층에서 마지막 요소값들(1, 7, 19, 37, 61, ...)에서 다음과 같은 규칙을 찾았다.

다음 계층 요소의 마지막 요소값 = 이전 계층의 마지막 요소값 + 6 * 이전 계층의 값

2계층의 마지막 요소값 = 1 + 6*1 = 7
3계층의 마지막 요소값 = 7 + 6*2 = 19
4계층의 마지막 요소값 = 19 + 6*3 = 37
5계층의 마지막 요소값 = 37 + 6*4 = 61
...

 

우선 무한 반복문을 생성하였다.

그리고 종료 조건으로 입력 받은 N의 크기가 (특정 계층의) 마지막 요소값 보다 클 경우로 설정하였다.

그리고 1회 반복이 될 때마다 지나가는 방 개수(count)가 1씩 증가하도록 하였다.

 

지나가는 방 개수(count)의 초깃값은 1로 설정하였다.

(입력 받은 값(N)이 1이 될 경우, 무한 반복문은 동작하지 않게 되고, 결국 초깃값 1이 출력된다.)

 

최종적으로 count 변수의 값을 출력하도록 하여 문제를 해결하였다.

 

코드

#include <iostream>
using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N, lastValue, count;

    cin >> N;

    lastValue = 1;
    count = 1;
    while (N > lastValue) {
        lastValue = lastValue + (6 * count);      // 7, 19, 37, 61, ...
        count++;
    }

    cout << count << endl;

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 1]