Baekjoon 2292번 : 벌집
포스트
취소

Baekjoon 2292번 : 벌집

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

규칙성을 찾으면 간단하게 풀리는 문제다. 시계 방향으로 돌아가면서 매겨진 숫자들이 한 바퀴를 돈 육각 고리 모양의 모음을 한 층이라 할 때, 층의 마지막 숫자를 이어보자. 1, 7, 19, 37, 61… 다시 앞 숫자와의 차를 계산해 나열해보자. 6, 12, 18, 24… 빙고! 원하는 숫자가 몇 번째 층에 있는지는 쉽게 구할 방법이 생겼다.

그럼 한 층에 숫자가 여러 개인데 최단 거리는 어떻게 구하느냐…? 싶을 수 있는데, 중심인 1번에서 같은 층 안에 있는 숫자들로 향하는 최단 거리는 모두 똑같다. 못 믿겠으면 직접 하나하나 이어보자.

그러므로 코드는 이렇게 완성된다.

`// https://www.acmicpc.net/problem/2292 Baekjoon No.2292 벌집

#include <iostream>
using namespace std;

int main() {
    int n;
    int route = 1; 
    int tmp = 1;
    cin >> n;
    if (n != 1) {
	while(1) {
	    if(tmp >= n) {
		    break;
	    }
	    tmp += route*6;
	    route++;
	}
    } 
    cout << route << endl;
    return 0;
}`
This post is licensed under CC BY 4.0 by the author.

백준 문제 찾기 귀찮을 때 터미널에서 바로 열기

급할수록 돌아가라.

Comments powered by Disqus.