백준 2292번 문제(벌집) C++로 풀기
문제 요약
벌집의 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을 더한 값을 출력하면 정답을 구할 수 있다.
주의점
방 수를 구할 때 시작 방과 끝 방을 모두 세야 한다는 것을 기억해야 한다.
Author And Source
이 문제에 관하여(백준 2292번 문제(벌집) C++로 풀기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@doctorson11/백준-2292번-문제벌집-C로-풀기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)