[백준알고리즘-JAVA]2292번 풀이(벌집)

안녕하세요

인포돈 입니다.

백준 알고리즘 2292번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2292 (벌집)

 

문제

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

입력

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

출력

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

입력 예시

13

출력 예시

3

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int out = Integer.parseInt(br.readLine());
		
		int loop = 1;
		int trap = 1;
		
		if(out != 1) {
		for(int i = 6; out > trap ; i+=6) {
			loop += 1;
			trap += i;
		}}
		
		System.out.println(out < 0 ? "정수 입력" : loop);
		
		}
		}

 

벌집 알고리즘에서 가장 핵심은 바로 패턴을 알아야 하는 것이라고 생각합니다.

 

우선 그림을 계속 봐보세요. 이웃하는 방까지 가는 최소 거리를 어떻게 세야 할까요?

(힌트는 1번부터 주위로 시선을 돌리면서 봐보세요)

 

 

---

STEP 1 패턴 찾기

정답은 바로 1 - 7 - 19 - 37 - 61 규칙이 보이시나요?

벌집을 자세히 보시면 가장 안쪽 레이어는 1

두 번째 레이어는 2 ~ 7

세 번째 레이어는 8 ~ 19....

이런 식으로 안에 레이어를 감싸는 부분이 있다는 것을 알 수 있습니다. 이레 이어가 같다면? 최소거리가 똑같아 보이지 않나요?

 

역시 예시만큼 쉽게 이해할 수 있는 게 없습니다.

만약 주어진 숫자가 1이라면?   바로 1이 출력되면 됩니다.

만약 2 ~ 7의 숫자라면?          2가 출력이 되게 됩니다.

그럼 8 ~ 19는 3, 20 ~ 37은 4 이런 식으로 출력이 되어야 하죠.

 

그럼 이제 1 / 7 / 19 / 37 / 61이 무슨 관계를 보이는지 알아야 합니다.

1     7         19        37         61

  +6    +12       +18      +24

 

위와 같은 규칙이 생기게 되죠.

 

이 규칙만 찾으셨다면, 이제 벌집 알고리즘은 쉽게 풀이가 가능하게 됩니다.

 

알고리즘 흐름도를 간략히 생각해볼 수 있죠

입력받기 -> 받은 입력 범위별로 구별하기 -> 구별한 값 출력

 

받은 입력 범위별로 구별하기는 각자의 식대로 해결하시면 되는데, 저의 예시를 설명해 드릴게요

 

저 같은 경우는

loop : 최소한의 방을 지나는 개수 즉, 출력이 되는 값을 표현한 변수

trap : 1 / 7 / 19 / 37.... 값을 표현하는 변수

 

예를 들어 입력 예시 13이 들어왔다고 가정하고 해당 코드를 따라가 봅시다.

 

1. 반복문 안 돌았을 경우 : loop = 1 / trap = 1 / out = 13

2. 반복문을 1번 돌았을 경우 : loop = 2 / trap = 7 / out = 13

3. 박복 문을 2번 돌았을 경우 : loop = 3 / trap = 19 / out = 13

4. 반복문을 3번 돌았을 경우 : 해당 반복문은 조건을 만족하지 못해 반복하지 못한다.

5. loop 출력

 

이런 식으로 돌아가게 됩니다.