BOJ 2292번 : 벌집

안녕하세요. 지난 포스팅의 BOJ 1712번 - 손익분기점에서는 math 라이브러리를 이용해서 수학 문제를 풀어보았습니다. 오늘은 수열과 관련된 문제를 풀어보도록 하죠. 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 계차수열(progression of differences)

제출 코드

N = int(input())

if N == 1 : print(1)
else :
    k = 1
    while True :
        if 3*k**2 - 3*k + 2 <= N and 3*k**2 + 3*k + 1 >= N :
            print(k + 1)
            break
        k += 1

 

해설

이 문제의 핵심은 계차수열임을 빠르게 파악하는 것입니다. $N$의 범위에 따라서 결과는 일정하다는 것을 관찰할 수 있죠. 

 

$$\begin{align*} N = 1 &\rightarrow 1 \\ 2 \le N \le 7 &\rightarrow 2 \\ 8 \le N \le 19 &\rightarrow 3 \\ 20 \le N \le 37 &\rightarrow 4 \\ 38 \le N \le 61 &\rightarrow 5 \\ &\vdots\end{align*}$$

 

따라서, $N = 1$일 때는 제출코드와 같이 일단 따로 출력을 해주겠습니다. 나머지 경우에서 시작지점의 규칙을 파악해보도록 하죠.

 

$$2, 8, 20, 38, 62, \dots $$

 

특별한 규칙이 없어보이지만 각 수열은 +6, +12, +18로 더해지는 숫자가 $6k$의 등차수열을 이루고있습니다. 이와 같이 더해지는 숫자가 규칙이 존재하는 수열을 계차수열이라고 합니다. 그리고 계차수열의 일반항은 $a_{1}$을 수열을 첫번째 항, $b_{k}$를 더해지는 수열의 일반항이라고 할 때 아래와 같이 쓸 수 있습니다. 

 

$$a_{n} = a_{1} + \sum_{k = 1}^{n - 1} b_{k}$$

 

이를 정리하면 시잠점의 수열의 일반항은 $3n^{2} - 3n + 2$임을 알 수 있습니다. 이와 동일한 방법으로 끝점의 수열의 일반항 역시 $3n^{2} + 3n + 1$임을 알 수 있죠. 이때, 저희는 $N$이 어떤 범위에 들어가는 지 파악해야하기 때문에 while 문을 이용해서 조건에 맞는 k를 찾아주고 결과를 얻으면 break 구문으로 반복문을 탈출해주면 됩니다. 

 

이와 같이 간단한 수학지식을 이용해서 풀 수 있는 문제들이 많기 때문에 평소에도 수학공부를 해놓으신다면 빠르게 풀 수 있는 문제가 더욱 늘어나실겁니다. 

 

참고자료 및 그림출처

백준 코딩 문제