백준 (2292번) - 벌집
2292번: 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌
www.acmicpc.net
문제
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
출력
입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
입출력 예제
설명
- 위에서 설명한 문제는 간단하게 1번 방에서 n번 방까지 가는 거리를 찾는 문제 입니다. 문제를 잘 보면 하나의 규칙을 찾을 수 있는데, 1번방에서 한번의 거리를 이동할 때 벌집의 개수는 6의 배수로 이루어 집다는 규칙 입니다. 이런 규칙에 맞게 임이의 숫자n이 주어지면 1부터 시작해서 6의 배수를 더해가며 거리를 ++ 하면 됩니다.
(distance) (checkNumber)
1번방과의 거리 벌집 번호 벌집의 증가 개수 (1번을 제외하고 6의 배수)
1 1 1
2 2 ~ 7 6
3 8 ~ 19 12
4 20 ~ 37 18
5 38 ~ 61 24
위의 조건으로 예제를 풀어보자 n = 18일 때 총 distance를 구해보자.
우선 distance = 1; checkNumber =1; n=18; 이다.
**** 첫번째 반복 ****
1. 벌집 번호(checkNumber) 보다 큰지 확인하고 checkNumber(1) 보다 n(18) 이 크기 때문에 checkNumber의 구간을 다음 구간의 가장큰 값으로 변경한다 <=== ( checkNumber == 7 )
2. 1번의 결과로 최소 n은 1보다 크다는 걸 알았기 때문에 거리를 +1 한다. <=== ( distance == 2 )
( checkNumber == 7, distance == 2)
**** 두번째 반복 ****
1. 벌집 번호(checkNumber) 보다 큰지 확인하고 checkNumber(7) 보다 n(18) 이 크기 때문에 checkNumber의 구간을 다음 구간의 가장 큰 값으로 변경한다 <=== ( checkNumber == 19 )
2. 1번의 결과로 최소 n은 7보다 크다는 걸 알았기 때문에 거리를 +1 한다. <=== ( distance == 3 )
( checkNumber == 19, distance == 3)
**** 두번째 반복 ****
1. 벌집 번호(checkNumber) 보다 큰지 확인하고 checkNumber(19) 보다 n(18) 이 작기 때문에 더이상 다음 구간으로 가지않고 반복을 끝낸다. <=== 이 때 거리는 늘어나지 않고 최종 거리 distance를 출력한다. 결과는 3
( checkNumber == 19, distance == 3)
이렇게 구간을 6의 배수를 단계별로 더해가면서 해당 구간에 들어가는지 확인해서 거리를 증가 시키는 방법이다.
혹시라도 n의 값을 한번의 연산으로 거리를 구할 수 있는지 고민을 해봤지만... 결국 패턴을 찾지 못해서 단순하게 풀었다. 혹시라도 더 좋은 답을 보신다면... 댓글로 알려줬으면 좋겠다. ~
설명이 엄청나게 길었는데 사실 코드로보면 엄청 짧다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
// 2292번 벌집
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
int distance = 1;
int checkNumber = 1;
while(true) {
if(n <= checkNumber) break;
checkNumber += (distance) * 6;
distance++;
}
System.out.println(distance);
}
}
|
cs |