백준/2292번 :: 벌집 (Java 자바 구현) 알고리즘 풀이

 

※ 문제 풀이 코드는 맨 아래에 있습니다.

 

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 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 Ex2292 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.print(solution(n));
    }
    
    private static int solution(int n) {
        // 1: 1 (1)
        // 2 ~ 7 : 2 (6개)
        // 8 ~ 19 : 3 (12개)
        // 20 ~ 37 : 4 (18개)
        // 38 ~ 61 : 5 (24개)
        // ...생략..
        // a(n) = a(n-1) + 6(n-1) | a(n): 첫 항
        if(n == 1) return 1;
        int i=2;
        int k=1;
        
        while(i<=n) {
            i += 6*k++;
        }
        
        return k;
    }
}​

 

1이 나왔을때는 1이라는 값이 나와야 한다. 2부터는 규칙을 가지게 된다. 처음 항만 살펴보면 2, 8, 20, 38, 62 ... 순이다. 

 

8 = 2 + 6*1

20 = 8 + 6*2

38 = 20 + 6*3

62 = 38 + 6*4

...생략...

 

따라서, a(n) = a(n-1) + 6*(n-1) (단 n > 1)을 만족한다.

 

결과

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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