백준 2292 벌집 - 등차수열 : 고등학교 수학문제 (Java)

알고리즘이 큰 영향을 미치지 않던 시절 시험 한두번 정도 접해본 적은 있었다.
그때 느낀 생각. 아 이게 연필로 푸는 수학문제면 잘 풀 텐데...
기본적인 중고등학교 수학 개념을 이해해야 풀 수 있는 문제 좋아함.
이번 문제가 딱 그랬음.

---

 

위의 그림과 같이 육각형으로 이루어진 벌집이 있다.

그림에서 보는 바와 같이

중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다.

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지

(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오.

예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

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

출력

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

---

문제 조건에서 처음과 끝을 포함하므로, 해당 방 번호가 몇 층에 있는지, 즉 층수 n이 출력해야 할 정답이 된다.

그럼 벌집의 방 번호를 한번 층별로 분석해보자.

 

1	1층	1개
2 3 4 5 6 7	2층	6*1개
8 9 10 11 12 13 14 15 16 17 18 19	3층	6*2개
20 21 22 .... (중간생략) .... 35 36 37	4층	6*3개

이런식으로  n층에는 6*(n-1)개의 방이 있다.

 

2층 이상일 때 각층 맨 마지막 방을 수식으로 나타내보자.

7 = 1 + 6*1

19 = 1 + 6*1 + 6*2

37 = 1 + 6*1 + 6*2 + 6*3

...

혹시 감이 좀 오는가?

1 + 6*(1 + 2 + .... + n-1)

= 1 + 6* ((n-1)*n/2)

= 3n^2 - 3n + 1

이 각층 마지막 방 번호가 된다.

 

(고등학교 수학의 수열을 배웠다는 전제 하에 작성 중인 글이다.

이 수식 전개가 이해가 되지 않는다면 등차수열의 합에 대해 검색해보고 와야 한다..ㅠㅠ

수식 에디터가 하나 있으면 좋긴 하겠는데 내가 못 찾는 건가..)

 

그리고 1이 입력되는 경우라면, 1층이라고 예외 처리를 뱉어줘야 한다.

 

그리고 입력받은 방 번호가 각층 마지막 방 번호로 아까 구한 수식 3n^2 -3n +1 보다 크거나 같아질때까지,

작다면 계속 반복한다.

 

 

아, 3*(n^2) -3*n + 1으로 처음에 풀었을 때 에러났었다.

자바 언어는 거듭제곱을 구할때 ^를 지원하지 않는다는걸 잠시 망각.

 

그래서 내 풀이에서의 정답 코드는 아래와 같다.

 

import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException{
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		int num = Integer.parseInt(br.readLine()); 
		int n = 0; 
        
		if (num == 1){//들어온 방번호가 1이면 1층을 뱉어준다 : 예외처리 		
			n = 1; 
		} else { //각층 마지막 방번호 < 입력받은 방번호 라면 반복
			while((3*n*n - 3*n + 1) < num) {
				n++; 
			}
		} 
        
		System.out.print(n);
	}
}