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

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

 

입력

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

 

출력

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

 

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2004 B번

 

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

2292번: 벌집

풀이 : 

이 문제는 solved.ac 사이트에서 브론즈2에 배정된 문제이다.

티어만 놓고 본다면 쉬울 것이라고 생각하지만 그래도 나름 ACM에 나왔던 문제이기에 그렇게까지 쉽지는 않다.

 

그림과 눈으로 본다면 굉장히 쉬운 수학문제이지만 우리는 이것을 코드로 구현해야하기에 어렵다...

 

이 문제를 풀기에 앞서 수학적으로 찾을 수 있는 규칙성을 찾으려고 노력했고

 

그 결과, 

처음엔 1 

그 다음 원이 끝나는 부분은 7

그 다음 원이 끝나는 부분은 19

그 다음 원이 끝나는 부분은 37

 

즉 6n - 5 라는 수열이 보인다.

1번칸 (1개)은 1개, 2-7번칸 (6개)은 2개, 8-19번칸 (12개)은 3개, 20-37번칸 (18개)

 

그래서 이에 따라 자바(JAVA)를 사용하여 작성해 보았다.

import java.util.Scanner;
public class Main {
    public static void main(String []args) {
        Scanner sc = new Scanner(System.in);
        int number = 1;
        int rule = 6;
        int first = 1;
        int back = 1;
        int first_rule = 0;
        int back_rule = 6;
        int input = sc.nextInt();
        
        while(true) {
            if(first <= input && back >=input) {
                System.out.println(number);
                break;
            }
            if(first == 1)
                first++;
            else 
                first += first_rule;
            back += back_rule;
            number++;
            first_rule += rule;
            back_rule += rule;
        }
        
        
        
    }
}
 
 

막상 풀어보니 간단한 수학 문제 였다.

 

나는 보통 이런 문제를 풀기전에 우선 사용 할 수 있는 알고리즘이 있는지, 어떤 식으로 접근하는게 좋은지부터 생각을 많이 해본다.

 

그 이후에 수학적으로 발견할 수 있는 규칙성을 찾기위해 손으로 노트에 일일이 적어가면서 찾아내는 편이다.

 

내 풀이가 완벽하다는 것이 아니다.

알고리즘을 풀이할때는 남의 소스코드도 보면서 참고하는 것이 도움이 많이 되기에 많은 분들에게 도움이 되었으면 하는 바램이다.