[백준] 2292 - 벌집

백준링크 : 바로가기 

#수학

수학적 사고를 요구하는 문제들의 향연입니다. 스터디에서 [백준 문제 - 단계별로 풀어보기]를 순서대로 부수고 있는데 다다음주까지 수학과 재귀에 고통받을 것 같습니다.

벌집 문제의 난이도는 solved.at 기준 브론즈 2여서 수학적 규칙을 찾는 건 나름 괜찮습니다. 다만 로직으로 구현해내기가 생각보다 쉽지 않습니다. 외국에서 한국어로는 알겠는데 그 나라 말로 어떻게 표현해야 할지 모르는 상황과 유사합니다.

벌집 문제 규칙의 핵심은 벌집의 규모가 어떤 규칙을 가지고 커지는가 입니다. 저는 규칙을 찾을 때 손으로 종이에 쓰는 편입니다. 벌집이 커질 때마다 시작 숫자와 끝 숫자를 찾아 둘레의 크기(끝 숫자 - 시작 숫자 + 1)를 구하다보면 6의 배수로 증가함을 알 수 있습니다. 

규칙을 찾았으니 문제가 요구하는 숫자가 주어졌을 때 중심으로부터 몇 개의 벌집을 거쳐 닿을 수 있는지 출력해줘야 합니다. 주어진 숫자 X가 2인 경우 정답은 2 입니다. 즉, 시작점인 1도 경로에 포함시켜야 합니다. 

제가 생각한 로직은 주어진 숫자 X에 +1씩 증가하는 n(n = 1)을  {X - (6 * n)} <= 0씩 빼가며 0보다 같거나 작아지면 멈추고 n을 출력하는 것입니다. 다른 분의 코드를 봐도 표현 방법만 다르고 로직은 같았습니다. 

(출처 : https://www.acmicpc.net/problem/2292)

실행 코드

import java.util.Scanner;

public class BeeHive_2292 {
    static int n;
    static int nMinus;
    static int cnt = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        nMinus = n - 1;

        //1이 주어지면 1을 그대로 반환
        if (n == 1) {
            System.out.println(1);
        }

        if (n != 1) {
            while (true) {
                //6의 배수로 맞추기 위해 시작점 1을 0으로 둠. 시작점을 count 하지 않기 때문에 출력 시 + 1을 해줘야됨.
                nMinus -= (6 * cnt);
                if (nMinus <= 0) break;
                cnt++;
            }
            System.out.println(cnt + 1);
        }
    }

}

백준에서 다른 분의 코드도 봤는데 훨씬 간결하게 구현했습니다. 시작점을 1이 아닌 2로 잡았고 벌집이 벌크업 될 때의 시작 숫자를 i로 뒀습니다. i는 6의 배수들의 합으로 증식합니다. while 문은 주어진 값 X보다 i 가 커지면 break 되는 조건을 설정했습니다. 그리고 정답 변수 k에 증가식을 넣어 6의 배수로 곱해주면서 시작점 1까지 포함해 정답을 출력했습니다. 

샘플 코드

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

public class BeeHive_2292_ex {

    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) {

        if(n == 1) return 1;
        int i=2;
        int k=1;

        while(i<=n) {
            i += 6*k++;
        }

        return k;
    }

}

 

하... 갈 길이 9만리 입니다. 정신줄 붙들어 매야 합니다.