2292번 벌집

벌집

풀이

번 칸이 번 칸으로부터 얼마나 떨어져 있는지를 구하는 문제입니다.

번 칸을 육각형들로 감싸 봅시다. 번 칸부터 번 칸이 번 칸을 감싸고 있는 것을 알 수 있습니다. 껍질을 씌우듯이 계속 감싸 봅시다. 다음은 번 칸부터 번 칸이 감싸고 있습니다. 이렇게 감싸다 보면 번호가 을 넘어서는 순간이 옵니다. 번호가 넘어서고 나서까지 감싼 횟수가 답이 됨을 알 수 있습니다.

이제 감싸는 데 필요한 칸의 개수가 어떻게 증가하는지만 알면 답도 쉽게 구할 수 있습니다.

관찰을 통해 로 의 배수의 나열임을 알 수 있습니다.

간단한 증명

어떤 껍질을 육각형으로 보고 육각형의 한 변을 이루는 칸의 개수를 이라 합시다. 예를 들어 첫 번째 껍질인 번 칸 부터 번 칸 까지는 개의 칸이 한 변을 이룹니다. 이 변의 길이는 껍질을 한 번 감쌀 때 마다 한 칸씩 늘어납니다.

이제 개의 칸이 한 변을 이루는 껍질을 한번 더 감싸는 데 몇 개의 칸이 필요한지 알아봅시다.

빨간색 부분이 첫 번째 껍질입니다. 6개의 칸들로 이루어진 육각형의 한 변의 길이는 칸입니다.

껍질의 윗부분과 아랫부분만 덮어봅시다. 그림에서 파란색 부분에 해당합니다. 각각 개의 칸, 총 개의 칸이 필요합니다.

이제 껍질의 왼쪽부분과 오른쪽 부분을 덮어봅시다. 그림에서 초록색 부분에 해당합니다. 각각 개의 칸, 총 개의 칸이 필요합니다.

이를 모두 더하면 총 개의 칸이 필요합니다.

변의 길이는 껍질이 없는 것 부터 시작해 로 씩 증가하고, 껍질을 이루는 칸은 이의 배가 필요하므로 로 의 배수임을 알 수 있습니다.

코드

def main():
    N = int(input())
 
    counter = 1
    dist = 1
 
    while counter < N:
        counter += dist * 6
        dist += 1
 
    print(dist)
 
 
main()