백준 2292번 파이썬 풀이: 벌집

백준 2292번 벌집

 

알고리즘 분류: 수학

 

링크: https://www.acmicpc.net/problem/2292

 

2292번: 벌집

문제

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

입력

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

출력

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

 

 

문제 파악

 

이 문제는 벌집모양으로 구성되있는 수들의 규칙을 파악해내는게 핵심이다.

 

입력값이 10억까지 주어질 수 있기 때문에 시간복잡도가 큰 알고리즘은 시간초과가 나기 쉬운문제이다.

 

벌집의 규칙을 파악해보자면 처음 가운데에 1이라는 숫자가 있고 이를 육각형 모양으로 6개의 숫자가 감싸고있다.

 

그리고 그 밖을 또 12개의 숫자가 감싸고있다.

 

여기서 벌집모양으로 감싸져 있는 수들의 규칙을 파악하자면

 

1

1 + 6

1 + 6 + 12

1 + 6 + 12 + 18

 

계속해서 바깥 테두리에있는 숫자의 개수가 6의 배수로 늘어난다는 규칙을 발견할 수 있다.

 

그래서 이 테두리 하나씩을 한개의 라인이라고 생각하고

 

n이 어느 라인에 속해있는지를 찾아서 출력을 해줄생각이다.

 

 

코드

# 2292번

n = int(input())

line = 1
next_num = 1

if n == 1:
    print(1)
else:
    while True:
        if n <= next_num:
            print(line)
            break
        
        next_num += (6 * line)
        line += 1 

입력값이 10억까지 주어질 수 있어서 나름대로 최대한 시간복잡도를 줄여보려고 생각했고

 

여러번의 시간초과를 겪고나서 만들어낸 코드이다.

 

앞서 말했듯이 n이 몇번째 라인에 속해있는지를 찾고 그 라인을 출력해주면 되기 때문에

 

한 라인에서 제일 높게 나올수있는 수를 next_num이라는 변수로 저장하고

 

한 라인을 지날때마다 6의 배수로 증가시킨다.

 

n이 next_num보다 작거나 같다면 n이 그 라인에 속해있다는 뜻으로 받아들인다.

 

처음에 코드를 짜면서 만약 두번째 라인에 있다면 2이상 7이하로 해야되지 않을까라고 생각했는데

 

next_num가 1에서부터 차근차근 증가하다보니 굳이 그 조건을 넣지않아도 충분히

 

몇 번째 라인에 속해있는지를 찾을 수 있다.