[JAVA] 백준 2292번 벌집 : 부등식과 반복문 1

2292번: 벌집

 

1. 문제 추상화

 

벌집은 정육각형을 동일한 정육각형으로 한 층씩 둘러 쌓아서 만든다.

한 층에 속한 정육각형들은 중심에서 떨어진 거리가 모두 동일하다.

그러므로 입력받은 번호의 정육각형이 몇 번째 층에 속하는지 구하라. 

 

 

2. 알고리즘

 

층(n)	최솟값	최댓값
1층	x	1
2층	2	7
3층	8	19
4층	20	37
5층	38	61
	. . .	. . .

 

1. 각 층(n)의 최대값의 수열의 공차는 6의 등비수열을 이룬다.

 

1 7(1+6) 19(7+6*2) 31(19+6*3) .....

▷ a₀ = ₁

▷ a_n = a_n-1 + 6(n-1)

 

2. 반복문으로 n을 1씩 증가하여, 입력받은 수보다 큰 최대값 탐색한다.

3. 최대값을 탐색하면 최대값과 대응되는 n을 출력한다.

 

3. 패착

 

쉬운문제지만 어렵게 풀었다.

그 이유는 반복문은 부등식에 효과적임을 알지 못했다.

 

입력값이 n층에 속함을 증명하려면 두 가지가 입증되어야 한다.

 

1. 입력값이 n층의 최솟값보다 같거나 커야한다.

2. 입력값이 n층의 최댓값보다 같거나 작아야한다.

 

그래서 나는 1번과 2번을 모두 코드로 구현하려 했다. 그러나 그럴 필요가 없다. 입력값이 한층의 최대값보다 큼이 증명되면 자동으로 입력값은 다음 층의 최솟값보다 같거나 작음이 입증된다.

 

이것이 반복문의 가장 큰 무기이다.

 

반복문은 과거 - 현재 - 미래 가 있다. 과거는 모두 조건에 부합한 '사실'들이다. 그리고 현재는 '사실'들 위에 있다. 그러므로 부등식, 수열 같이 이전과 이후가 있는 수학은 반복문이 효과적이다.

 

4. 풀이

 

내 풀이 

반복문의 이점을 살리지 못하고, 최댓값과 최솟값을 수식 구하여 조건문을 만들었다. (정말 어렵게 풀었다;;)

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int value = sc.nextInt();
		int i = 0;
		
		while(true) {
			// 반복문의 이점을 살리지 못하고 최댓값과 최솟값을 모두 조건문에 포함시켰다.
			if( value <= 3*i*i-3*i+ 1 ) { // 최댓값보다 작은가?
				if( value >= 3*i*i -9*i + 7 ) { // 최솟값 보다 큰가?
					System.out.println(i);
					break;
				}
			}
			i++;
		}	
	}
}

 

 

일반적인 풀이

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int value = sc.nextInt();
		int pivot = 1;
		int i = 1;
        
        // 이전과 이후과 있는 수열과 부등식 풀이에 반복문은 적합하다.
		while(value > pivot) { // 과거는 이미 증명됨
			i++;
			pivot = pivot + 6*(i-1); // 과거를 통해 현재를 유추
		}
		System.out.println(i);
	}
}