[백준, python 파이썬] 2292번 : 벌집(기본 수학1)

백준 2292번 문제 풀기

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

2292번: 벌집

---

문제 설명

문제

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

입력

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

​

출력

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

 

예제 입력 1	예제 출력 1
13	3

---

알고리즘 및 설명

문제는 복잡해보여도 코드는 간단하게 구현할 수 있는데, 기본 수학 파트는 문제에서 규칙을 찾는 것이 가장 중요한 것 같다. 내가 구현한 코드는 아래와 같다.

 

N = int(input()) ## 입력값 받기
num = 1 ## 초기 숫자 1의 벌집 개수는 1개
for i in range(N):
    num += i*6  ## i 번째 겹인 벌집 개수는 6의 배수로 늘어남 (num : 벌집 개수 누적)
    if N <= num: ## 벌집 개수의 누적이 입력값보다 커지면
        print(i+1) ## (i+1)번 째 겹인 것이므로 출력!
        break

 

이걸 하나씩 풀어서 생각해보면, 아래와 같다.

[2, 3, 4, 5, 6, 7] ==> 1 [8, 9, ... ,     19] ==> 2 [20, 21, ...,   37] ==> 3 ...

처음에 출력값이 1이 되는 입력값은 2부터 7까지로 1보다 큰 6개의 자연수이다.

다음에 출력값이 2가 되는 입력값은 8부터 19까지로 7 다음 순서대로 12개의 자연수이다.

즉, 출력값이 C인 숫자는 C * 6개가 존재한다.

이 규칙을 사용하면, 숫자 N이 있을 때 이 숫자가 (1+6*(1+...+(i-1)) < N ≤ (1+6*(1+...+i)) 일 때의 i를 구하면 그것이 출력값이 된다.