Java - [백준] 2292번 : 벌집

1. 문제

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

2292번: 벌집

• 입력 : 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
• 출력 : 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력

---

2. 생각

본 문제는 계차 수열을 이용하여 풀었다. 

 

계차 수열 알고리즘을 이용한 이유는 다음과 같다.

• ex) N = 2 일 때는 2 개의 방을 이동해야 하며,
• ex) N = 8 일 때는 3 개의 방을 이동해야 한다. 
• 위 몇 가지 예시들을 통해 아래의 표와 같이 n 값에 따라 규칙성이 나타남을 확인할 수 있었다.
  
  

출처) https://st-lab.tistory.com/73

위 표를 보면  N 값이 1, 7, 19, 37, 61 ...을 기준으로 이동하는 방의 갯수가 변하는 것을 확인할 수 있다. 즉, "입력 받은 값, N이 어느 영역에 속해 있는가?"에 따라서 이동하는 방의 갯수가 결정됨을 확인할 수있다. 

 

Q) "N이 어느 영역에 속해있는가?" 에 대해서는 어떻게 알 수 있는가?

범위의 끝 값인 1, 7, 19, 37, 61 ...을 살펴 보면 각각의 값들이 6, 12, 18, 24 .... , 6의 배수로 차이가 발생함을 찾을 수 있다. 즉, 범위의 끝 값들은 6의 배수로 계차 수열을 이루고 있음을 확인할 수 있다. 이 점을 이용하여 "N보다 큼과 동시에 N과 가장 가까운 계차 수열을 찾는다." 을 통해 N이 속해있는 영역을 찾을 수 있다.

---

3. 풀이 및 코드 분석

int count = 1;

if(n!=1) {
    while(1+3*count*(count-1)<n) 
         count++;		
}

• count : 이동한 방의 수
• if, n = 1이라면 생각할 필요 없이 count = 1이기 때문에 n != 1인 경우에 대해서만 생각한다.
• n보다 큼과 동시에 n과 가장 가까운 계차 수열을 찾기 위해서 계차 수열의 합을 구한다.
  ▶ 7 인 경우 : 1 + 6 = 1 + 6 x (1)       → count = 2
  ▶19 인 경우 : 1 + 6 + 12 = 1 + 6 x (1+2)       → count = 3
  ▶37 인 경우 : 1 + 6 + 12 + 18 = 1 + 6 x (1+2+3)       → count = 4
  
  ▶n과 큼과 동시에 가까운 계차 수열은 1 + 6x(1+2+3+ ... + count-1) = 1 + 3 x (count-1) x count 이다.
  
  

import java.io.*;

public class P2292 {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(reader.readLine());
		int count = 1;

		if(n!=1) {
			while(1+3*count*(count-1)<n) 
				count++;		
		}

		writer.write(count+"\n");
		writer.flush();
		reader.close();
		writer.close();
	}
}

---

4. 메모

연습, 연습, 연습