백준 2292번 문제(벌집) C++로 풀기

2292번 벌집 링크

---

문제 요약

벌집의 1번 방부터 입력으로 주어진 방까지 최소한 지나야 하는 방의 수를 출력한다.

---

코드

#include <iostream>

using namespace std;

int main()
{
  int n;  // 입력
  cin >> n; 
  int result=0; // 출력
  int round=0;  // 바퀴 수
  int maxroom=1;  // round 바퀴에서의 숫자가 가장 큰 방
  while(1)
  {
    maxroom += 6*round;  // round마다 maxroom 구하기
    if(maxroom>=n)  // n이 maxroom이하일 때 해당 round를 구한다
    {
      result=round+1; // 끝 방도 세줘야 하므로 +1
      break;
    }
    round++;
  }
  cout << result;
}

---

풀이

최소한으로 지나야 하는 방의 수를 구하기 위해서는 입력으로 주어진 n 번째 방이 어느 바퀴에 위치해 있는지 알아야 한다. 바퀴란 일련의 숫자들의 방이 모여 원형을 이루고 있는 모양을 말한다.

벌집 문제에 나온 그림을 볼 때, 1번 방은 1번째 바퀴에 있고, 2~7번 방은 2번째 바퀴에, 8~19번 방은 3번째 바퀴에 위치한 것을 볼 수 있다.

바퀴가 늘어날수록 한 바퀴에 위치해 있는 방들 중 가장 큰 숫자를 가진 방은 6의 배수 형태로 그 수가 증가하는 것을 알 수 있다.

예를 들어 2번째 바퀴에서 가장 큰 수를 가진 방은 7이고, 3번째에선 19인데, 1번째 바퀴에서 가장 큰 수를 가진 방인 1과 비교했을 때 1번째 바퀴에서 2번째 바퀴로 넘어갈 때엔 숫자가 6이 증가하고, 2번째에서 3번째로 갈 때는 12가 증가하는 식이다.

그리고 바퀴 수는 곧 최소한으로 지나가야 할 방의 수와 일치하므로, 끝 방을 고려해 바퀴 수에 1을 더하면 출력값을 구할 수 있다.

이를 이용하여, 바퀴마다 가장 큰 수를 가진 방을 구해 입력으로 받은 방이 어느 바퀴에 있는지 알아내고, 거기에 1을 더한 값을 출력하면 정답을 구할 수 있다.

---

주의점

방 수를 구할 때 시작 방과 끝 방을 모두 세야 한다는 것을 기억해야 한다.