[JAVA / 자바] 백준 2292번 - 벌집

문제

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

---

입력

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

---

출력

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

---

 

---

문제 접근 방법

문제의 패턴을 찾는 게 중요하다.

1번 방부터 시작해서 n번방까지 가는 최소 거리를 구하는 것으로 1번 방으로부터 몇 겹이 떨어져 있는지만 구할 수 있으면 쉽게 풀 수 있는 문제가 된다.

항상 시작은 1번 방이므로

1번 방으로부터 ~

  2~7번 방까지 : 1겹

  8~19번 방까지 : 2겹

  20~37번 방까지 : 3겹

  38~61번 방까지 : 4겹

  ...

이런 형태를 띠고 있다.

이때, 1겹이 추가될 때마다 1번 방으로부터 거리가 1씩 늘어난다. 즉, 이 말은 n번방이 1번 방과 몇 겹이 떨어져 있는지만 알면 된다는 것인데 위 수열은 계차수열의 형태를 띠고 있다. 바로 다음 겹은 이전겹의 방보다 6개가 더 많다는 것이다. 예를 들어 1겹의 방 개수가 6개이면, 2겹의 방 개수는 12개이다. 그렇다면 이를 바탕으로 문제를 풀어주면 될 것이다.

---

JAVA 코드 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int temp=1, step=1;
        while(temp < num){
            temp += 6*(step++);
        }
        System.out.println(step);
    }
}

코드 실행 결과

---

후기

수열을 찾아주면 이번 문제는 쉽게 풀 수 있는 문제라 생각한다.

---

문제 원본

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