- 벌집이 형성되는 규칙에 따라 벌집의 위치를 구하는 문제
https://www.acmicpc.net/problem/2292
1. 문제
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
2. 문제 접근
- 입력의 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
- 단, 반복문을 사용하면 시간 복잡도가 커지니 문제에서 규칙을 찾아서 수학적으로 계산할 수 있도록 유도하자!!
핵심!
- 출력 값에 따라 입력 값들을 나누어 보자.
출력 값
- 1 -> 1
- 2 -> 2~7
- 3 -> 8~19
- 4 -> 20~37
- 5 -> 38~61
입력 값들을 살짝 조작해보자. 1을 빼고 6으로 나누어보자.
출력 값
최소 지나는 방의 개수 | 방숫자의 범위 | (방숫자 -1 ) / 6 | 0부터 최소 지나는 방의 개수 -1 까지의 합 |
1 | 1 | 0 | 0 |
2 | 2 ~ 7 | 0보다 크고 1 이하 | 1 |
3 | 8 ~ 19 | 1보다 크고 3 이하 | 3 |
4 | 20 ~ 37 | 3보다 크고 6 이하 | 6 |
5 | 38 ~ 61 | 6보다 크고 10이하 | 10 |
- 즉, 입력 값이 n 이고 출력 값보다 1 작은 값을 t 라고 하면, 6(t^2 + t)/2 >= n-1 이 성립되고 t는 이 부등식을 성립하는 최소값이 될 것 이다. 다음을 이차 방정식의 해를 구하는 방법으로 구해보면
t는 다음을 만족하는 최소값이 될것이고 출력값 = t+1이 된다.
3. 코드
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Integer.parseInt(br.readLine());
N-=1;
int pass = (int)Math.ceil((-3+Math.sqrt(9+12*N))/(double)6);
System.out.println(pass+1);
}
}
'백준 > JAVA' 카테고리의 다른 글
[백준/JAVA] 2751번 수 정렬하기2 (0) | 2023.01.21 |
---|---|
[백준/JAVA] 2750번 수 정렬하기 (0) | 2023.01.21 |
[백준/JAVA] 2292번 벌집 (0) | 2023.01.21 |
[백준/JAVA] 9020번 골드바흐의 추측 (0) | 2023.01.21 |
[백준/JAVA] 11653번 소인수분해 (0) | 2023.01.20 |