[JAVA]백준 알고리즘 2292번 : 벌집

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

2292번: 벌집

문제

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

 

풀이

방의 번호를 입력받아 해당 방까지 가려면 최소 몇 개의 방을 지나가야 하는지 구하는 문제이다.

 

각 방까지 갈 때 몇 개의 방을 지나가야 하는지를 정리하면, 다음과 같다.

 

1번 방까지 갈 때 지나야 하는 방의 개수 : 1

2 ~ 7번 방까지 갈 때 지나야 하는 방의 개수 : 2

8 ~ 19번 방까지 갈 때 지나야 하는 방의 개수 : 3

20 ~ 37번 방까지 갈 때 지나야 하는 방의 개수 : 4

 

이를 그림으로 간단히 보면, 아래와 같다.

1번 방에서 주황색 선 안에 있는 방까지 가는 횟수는 2이고, 저런 식으로 밖으로 뻗어 나갈 때마다 해당 방까지 가는 횟수는 1씩 증가한다.

초록 선 위에 있는 방의 번호는 이 규칙을 적용했을 때 거리가 같은 방들 중 가장 번호가 큰 방의 번호이다.

이 방의 번호들은 규칙이 있는데, 아래를 보면 그 규칙을 알 수 있다.

 

1 = 1

7 = 1 + 6

19 = 1 + 6 + 12

37 = 1 + 6 + 12 + 18

61 = 1 + 6 + 12 + 18 + 24

 

이처럼 번호가 가장 큰 방들은 "초항과 공차가 6인 등차수열의 합 + 1"임을 알 수 있다.

따라서, 가장 번호가 큰 방들을 등차수열의 합 공식을 사용하여 식으로 나타내면 아래와 같다.

 

이를 이용하면 1번 방부터 n번 방까지 거리가 얼마나 되는지 구할 수 있을 것이다.

 

여기서 생각해야 할 것이 하나 더 있다.

문제에서 N의 범위가 1,000,000,000 (10억)으로 주어졌다.

그렇다면 배열의 크기를 3n(n - 1) + 1 >= 10억 을 만족하는 n으로 설정하면 될 것이다.

따라서 필자는 배열의 크기를 18,259로 설정하였다. (3 * 18,259 * 18,258 + 1 = 1,000,118,467이다.)

---

🔔 자세한 코드 설명은 더보기 란에 작성하였습니다.

1. 배열의 크기를 18260으로 설정하였다. (위에서는 18,259로 설정하였다고 했는데, 1 ~ 18,259까지 사용하기 위해 18,260으로 설정하였다.)

int[] six = new int[18260];

 

2. 위에서 구한 계산식을 사용하여 배열에 값을 넣는다.

for(int i = 1; i <= 18259; i++) {
    six[i] = 3 * i * (i - 1) + 1;
}

 

3. N을 입력받고, 거리를 출력한다.

int N = Integer.parseInt(br.readLine());
for(int i = 1; i <= 18259; i++) {
    if(N <= six[i]) {
        System.out.println(i);
        break;
    }
}

 

*배열에 저장되는 수를 순서대로 몇 개 나열하면, 1 - 7 - 19 - 37 - 61 -...이다.

 

N이 1보다 작거나 같다면, 거리는 1

N이 7보다 작거나 같다면, 거리는 2

N이 19보다 작거나 같다면, 거리는 3

N이 37보다 작거나 같다면, 거리는 4

N이 61보다 작거나 같다면, 거리는 5이다.

 

따라서 N을 배열의 값과 비교하고, N이 해당 배열의 값보다 작거나 같다면 해당 배열의 index를 출력하면 된다.

---

코드

BufferedReader 클래스와 StringBuilder 클래스를 이용한 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] six = new int[18260];
        for(int i = 1; i <= 18259; i++) {
            six[i] = 3 * i * (i - 1) + 1;
        }

        int N = Integer.parseInt(br.readLine());
        for(int i = 1; i <= 18259; i++) {
            if(N <= six[i]) {
                System.out.println(i);
                break;
            }
        }
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!