[BOJ 13522] 악마의 수열

오래간만에 글을 올리네요.

최근에 풀었던 "악마의 수열"이라는 문제가 꽤나 인상이 깊게 남아서 포스팅을 올립니다!

 

solved 기준 골드 1인 문제고, 개인적으로 골드1이라기엔 너무 쉬운 거 아닌가 싶지만, 그건 제가 주력이 수학이라 그런 거려나 생각합니다()

 

문제를 요약하면 다음와 같습니다.

 

"x_0=0, x_1=1, 그 뒤로는 앞 두 항의 평균으로 이루어진 수열에 대해서, x_n에서 0 뒤로 6이 몇개 연속하는지"를 묻는 문제입니다. 실제로 이 수열을 한번 구해볼까요?

 

엑셀로 빠르게 만들어 본 결과, 대략 이런 규칙을 가지고 나아가는 것을 알 수 있습니다. 무언가 점점 0.666.....으로 가까워지는듯한 기분이 들죠?

 

실제로 그런지를 확인하기 위해서는 수열의 일반항을 구해야 하는데, 평범한 등차/등비수열처럼 생기지는 않아서 일반항을 구하는 것이 그렇게 쉬워보이진 않습니다. 대강 2/3 근처로 가는 거긴 할텐데... 잘 모르겠네요. 귀납적으로 정의된 이 수열의 일반항을 구할 수 있을까요? 아니면 직접 규칙을 다 찾아봐야 할까요? n이 10^5이고, 소숫점 뒤로 찾으려면 실수 오차도 엄청날텐데요? 우린 망한 걸까요?

 

물론 (Wolfram Alpha 선생님을 사용하면) 이 문제는 해결할 수 있습니다! 이렇게 정의된 수열의 일반항을 구하는 과정은 아쉽게도 현행 고등학교 교육 과정에서는 빠졌지만, 다음과 같은 식으로 정리하면 구할 수 있습니다.

 

수식 입력 하는 게 영 시원찮아서, 아예 그냥 그림판으로 정리했습니다.

어쨌든, 결과를 보니 n이 커지면 커질수록 2/3에 가까워지는 것을 알 수 있습니다! 이제 문제의 목표인 "연속해서 나오는 6의 개수"에 한발짝 더 다가갔네요.

 

일반항을 자세히 보면, n이 짝수일 때는, 2/3보다 작은 값이 나오고, 홀수일 때는 큰 값이 나오는 것을 알 수 있습니다. 연속해서 나오는 6의 개수도 2/3보다 작을 때와 클 때 다를테니, n의 홀짝성을 기준으로 한번 나누어서 생각해 보겠습니다.

 

우선 n이 짝수인 경우, a_n은 2/3보다 작습니다. 작아지는 정도가 d라고 한다면, d*10^n이 2/3보다 작은 가장 큰 n자리까지는 6이 이어진다고 생각할 수 있습니다. 반대로 n이 홀수라면, a_n은 2/3보다 크고, 커지는 정도를 역시 d라고 하면 d*10^n이 1/3보다 작은 가장 큰 n자리까지 이어집니다. 두 경우 모두 d는 바로 뒤에 이어지는 2/3*(-1/2)^n(의 절댓값)이 되겠네요.

 

그렇지만 이를 그대로 계산하는 코드를 내기에는 n이 10만이라 시간도 걸리고, 컴퓨터 상에서 실수를 표현하는 이슈로 인해서 숫자가 일정 이상 작아지면 0이 되어서 표현하기 힘듭니다. 대신에 고등학교 수학에서 배우는 log를 사용하면 이를 만족하는 n을 금방 찾을 수 있습니다.

 

여러 가지 수학적인 부분을 담고 있는 문제지만, 그 안에서는 또 이 문제를 '프로그래밍'으로 해결하기 위한 배경 지식들이 조금 필요한 부분이 흥미로운 문제였다고 생각합니다!

 

Python 3 정답 코드는 다음과 같습니다. 식을 정리하고 정리하면 저정도로 정리가 되어서, 코드가 아주 짧게 나옵니다!

from math import log10
n=int(input())
lg2=log10(2)
if n%2:n-=1
print(int(n*lg2))

질문이나 잘못된 내용 등등 있으시면 댓글로 달아주시면 확인하겠습니다!