백준 2292 벌집

문제

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

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

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

예제 입력 1
13

예제 출력 1
3

풀이 과정

육각형의 방이 갈수록 6개씩 더 늘어난다는 것이 핵심이다.

먼저 시작 방에 0의 값을 주고 끝 방에 6의 값을 준다.
그리고 증가하는 방의 개수를 x로 두고 1을 주고, 지나는 방의 수의 변수에 2를 준다.
N이 1이면 지나는 방은 하나이므로, 1을 출력한다.
N이 2 이상이면 반복을 한다.
N - 1의 값이 시작 방보다 크고 끝 방 * 증가하는 방의 개수보다 작거나 같으면 종료하게 만든다.
조건을 만족하지 않으면 시작 방은 끝 방의 값을 가지고, x는 지나는 방의 개수만큼 증가, 지나는 방의 개수는 1 증가한다.

다른 풀이로 전체 방의 개수를 이용하는 것이 있다.
전체 방의 개수는 지나는 방의 개수와 같이 1로 둔다.
경로가 1 증가할수록 둘레의 방의 개수는 이전보다 6씩 더 증가하므로
반복 조건을 N이 전체 방보다 크게 한다.
그리고 경로가 1 증가하고 전체 방의 개수를 누적하고
방의 개수도 6 누적한다.

두 번째 풀이가 더 간단하고 이해하기 쉬웠다.

코드 1

N = int(input())
start_cell = 0
end_cell = 6
x = 1
route = 2
if N == 1:
    route = 1
else:
    while True:
        if start_cell < N - 1 <= end_cell * x:
            break
        start_cell = end_cell
        x += route
        route += 1
print(route)

코드 2

N = int(input())
total_cells = route = 1
cell = 6
while N > total_cells:
    route += 1
    total_cells += cell
    cell += 6
print(route)

백준 2292 벌집

좋은 웹페이지 즐겨찾기