[백준] 벌집 2292 [JAVA]

출처 : www.acmicpc.net/problem/2292

2292번: 벌집

문제

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

입력

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

출력

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

풀이법

- 다이나믹 프로그래밍을 써볼려 규칙성을 찾았다.

각 껍질의 개수의 증가하는 규칙을 찾아냈고, 최대 10억까지의 숫자는 몇 개의 배열이 필요할지 궁금했다.

- 바보같이 배열크기 지정보단 좀 더 동적인 방식으로 구현할 필요가 있을 것 같다.

 

 

코드

import java.util.Scanner;

public class Main {
	public static int execute(int N) {
		
		int[] answers = new int [1000001];
		int answer =0;
		
		// 구현하세요.
		if ( N == 1) {
			return 1;
		}
		
		answers [1] = 1;
		// dp 구현하기 
		for ( int i=2; i<= 100000; i++	) {
			answers[i] = answers[i-1] + 6*(i-1); // 2 = 1 + 6 , 3 = 2 + 12
		}
		for ( int i=1; i<= 100000; i++) {
			if ( N > answers[i-1]  && N <= answers[i] ) {
				answer = i;
				break;
			}
		}
		return answer; // 리턴값을 수정하세요
	}

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		System.out.println(execute(N)); // 3
	}

}