[백준알고리즘/기본 수학 1단계] 2292번 문제 : 벌집(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 2292번 문제 벌집을 풀어봤습니다

처음 문제에서 공식을 사용해서 풀은 기억이 있어서 공식을 찾다가 반복문을 사용하니 금방 풀린 문제입니다

ㅠㅜ 너무 어렵게 생각했어...

이제 제가 풀은 방법에 대해서 설명하겠습니다

 

---

문제 링크입니다

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

2292번: 벌집

 

문제

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

 

입력

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

 

출력

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

 

 

---

 

 

문제 풀이

문제를 푸는 방식은 벌집의 공식을 파악해야합니다

아래의 표를 보면

단계수가 늘어날 때마다 6의 배수로 방의 갯수가 늘어납니다

2 ~ 7까지는 2단계, 8 ~ 19까지는 3단계... 입니다

벌집단계	갯수	늘어나는 방 갯수
1	1	1
2	7	6
3	19	12
4	37	18
5	61	24

 

첫 번째 방법

첫 번째 방법은 while문을 사용했습니다

while문을 사용 Sum이 N보다 커지면 반복문을 종료합니다

반복문을 반복한 만큼 Count++을 하여 단계 수를 구합니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언 및 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		
		// Count 및 합계 초기값 세팅
		int count = 1;
		int sum = 1;
		
		// 합계가 N보다 커지는 경우 반복문 종료 -> 합계는 6의 배수만큼 계속해서 늘어난다
		while(N > sum)
		{
			sum += count * 6;
			count++;
		}
		
		// 결과 출력
		System.out.print(count);
	}
}

 

---

 

두 번째 방법

두 번째 방법도 위의 방법과 똑같이 구했습니다

나름 최적화한다고 한 방식인데 속도는 첫 번째 방법과 동일하게 나왔습니다 ㅠㅜ

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언 및 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		// Count 및 합계 초기값 세팅
		int count = 1;
		int sum = 1;
		
		// N이 1인 경우 1출력
		if(N == sum)
			System.out.print(1);
		else {
			while(true)
			{
				// 합계가 N보다 커지는 경우 결과출력 -> 합계는 6의 배수만큼 계속해서 늘어난다
				if(N <= sum) {
					System.out.print(count);
					break;
				}
				
				sum += count * 6;
				count++;
			}
		}		
	}
}

 

---

 

세 번째 방법

세 번째 방법은 단계 수를 구하는 부분을 메서드로 만들어서 구현하였습니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언 및 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		// 결과 출력 -> 벌집단계를 구하는 메서드 호출
		System.out.print(BeerHome(N));		
	}
	
	// 벌집단계를 구하는 메서드 선언
	static int BeerHome(int N)
	{		
		// Count 및 합계 초기값 세팅
		int count = 1;
		int sum = 1;

		// 합계가 N보다 커지는 경우 반복문 종료 -> 합계는 6의 배수만큼 계속해서 늘어난다
		while(N > sum)
		{
			sum += count * 6;
			count++;
		}
		
		return count;
	}
}

 

여기까지 세 가지 방법(?)으로 풀어봤습니다

이제 속도비교를 해보겠습니다

 

---

 

속도 비교

1. while문 사용

2. while문 사용(약간 최적화)

3. 메서드 사용

방법입니다

 

2번 방식이 나름 최적화를 해서 메모리가 약간 더 적게 든 것을 볼 수 있네요 ㅎ

굳이 메서드로 구현을 하지 않아도 되는 것을 메서드로 구현하여 3번을 보면 메모리와 시간이 더 걸렸네요

 

이상 백준알고리즘 2292번 벌집을 풀은 내용이었습니다

 

다음 문제 : 

이전 문제 : 2021.05.22 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 1단계] 1712번 문제 : 손익분기점(자바/JAVA)