[BOJ/백준] 2292번 벌집 C++ 문제 풀이

단계별로 풀어보기 - 수학 1 단계 - [3단계] 2292번

문제

문제 링크 : www.acmicpc.net/problem/2292

2292번: 벌집

입력 복사 : 

13

 

풀이

왼쪽 그림에서 처음 출발하는 1의 위치를 첫번째 육각형이라고 할때,

N이 위치한 육각형이 중앙으로부터 몇번째 육각형인지가 정답이라고 할 수 있다.

 

중앙에서부터 N까지 직선으로 이웃하는 방을 지나갈 때,

지나간 육각형 수만큼 최소 개수의 방을 거쳤다고 할 수 있기 때문이다.

 

 

왼쪽 그림에서 노란색으로 표시한 숫자들처럼 각 육각형에서 숫자가 가장 큰 숫자를 기준으로 몇번째 육각형인지를 구분합니다.

N이 육각형의 기준 숫자보다 큰 경우 다음 육각형으로 옮기고,

N이 육각형의 기준 숫자보다 작은 경우 N이 몇번째 육각형에 위치했는지 파악할 수 있습니다.

 

육각형의 기준 숫자는 end_of_hex라는 변수에 저장했습니다.

end_of_hex는 바깥쪽 육각형으로 이동할수록 증가하는데 다음과 같이

1,    7,   19,   37,   61˙˙˙

 +6  +12  +18  +24

으로 증가값이 6의 배수로 증가합니다.

증가하는 값을 표현하기 위해 증가값을 cnt라는 변수에 저장하였습니다.

cnt를 end_of_hex에 더하여 다음 육각형의 기준 숫자로 만들었으며, cnt는 이때마다 6씩 증가합니다.

 

 

CODE

#include <iostream>
using namespace std;

int main() {
	int N;
	int end_of_hex = 1, cnt = 6;
	int result = 1;
	cin >> N;

	while (1) {
		if (end_of_hex >= N) {
			cout << result << endl;
			return 0;
		}
		end_of_hex += cnt;
		cnt += 6;
		result++;
	}
}

 

결과