#2292 : 벌집

풀이방법

사용된 것:

수학

 

2022.04.23

주어진 벌집은 다음과 같이 여러 개의 겹으로 인식할 수 있다.

안쪽으로부터 몇 번째 겹에 있느냐에 따라, 그 칸에 도착하기까지 거치는 칸의 수가 정해진다.

17은 3번째 겹에 위치하므로, 17이 입력값으로 주어졌을 때 올바른 출력값은 3이다.

따라서, 주어진 수가 몇 번째 겹에 위치하는지를 알아내는 알고리즘을 작성하면 된다.

 

1번째 겹에 속하는 수는 1개이다.

2번째 겹에 속하는 수는 6개이다.

3번째 겹에 속하는 수는 12개이다.

4번째 겹에 속하는 수는 18개이다.

...

n번째 겹에 속하는 수는 6$\times$(n-1)개이다.

 

이러한 규칙을 이용하여, 각 겹에서 가장 큰 수를 저장하는 정수 배열을 생성할 수 있다.

N의 최댓값이 1,000,000,000이고 18300번째 겹의 가장 큰 수가 1,004,615,101이므로, 나는 18300번째 겹까지만 저장하였다.

 

길이가 18300인 이 정수 배열을 완성하면 다음의 수들을 저장하게 된다.

1, 7, 19, 37, 61, ... 1004615101

 

N이 주어지면,

이 배열에 저장된 수들을 앞에서부터 차근차근 점검해나가면서

N보다 크거나 같은 수가 발견되면 그 수의 인덱스에 1을 더한 값을 즉시 화면에 출력하고 반복문을 종료하면 된다.

겹의 번호는 1부터 시작하지만 배열의 인덱스는 0부터 시작하므로 1을 더해주어야 한다.

 

코드

Java(2022.04.23)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//각 겹의 가장 큰 수를 arr에 저장하기
		int[] arr = new int[18300];
		arr[0] = 1;
		int sum = 1;
		for(int i = 1; i<18300; i++) {
			sum += 6*i;
			arr[i] = sum;
		}
		
		//정답 구하여 출력하기
		for(int i = 0; i<18300; i++) {
			if(arr[i]>=n) {
				System.out.print(i+1);
				break;
			}
		}
		
		sc.close();

	}

}