리유나의 항해일지

문제 링크는 이쪽입니다. 0. 이 문제는 도대체 뭔가? 제가 BOJ에서 풀었던, 아니 PS를 하면서 풀었던 모든 문제를 통틀어서 가장 시행착오를 많이 겪었던 문제가 아마 바로 이 문제가 아닐까 싶습니다. 생각보다 유명한 문제여서 solved.ac 기준 루비 4임에도 불구하고 제법 많은 사람들이 풀었지만, 그럼에도 결코 쉬운 문제는 아닙니다. 개인적으로 적어도 난이도 값은 무조건 하는 문제라고 생각합니다. 문제의 내용 자체는 사실 아주 간단한데, 어떤 자연수 n에 대해서 n을 제곱수들의 합으로 나타내라는 것입니다. 사용된 제곱수의 개수는 최소여야 하고요. 가령, n이 25라면 3^2+4^2로도 나타낼 수 있겠지만 5^2 하나로 나타내는 것이 더욱 적합하겠죠. 그런데 n의 범위가 10^18까지의 자연수네요...

오래간만에 글을 올리네요. 최근에 풀었던 "악마의 수열"이라는 문제가 꽤나 인상이 깊게 남아서 포스팅을 올립니다! solved 기준 골드 1인 문제고, 개인적으로 골드1이라기엔 너무 쉬운 거 아닌가 싶지만, 그건 제가 주력이 수학이라 그런 거려나 생각합니다() 문제를 요약하면 다음와 같습니다. "x_0=0, x_1=1, 그 뒤로는 앞 두 항의 평균으로 이루어진 수열에 대해서, x_n에서 0 뒤로 6이 몇개 연속하는지"를 묻는 문제입니다. 실제로 이 수열을 한번 구해볼까요? 엑셀로 빠르게 만들어 본 결과, 대략 이런 규칙을 가지고 나아가는 것을 알 수 있습니다. 무언가 점점 0.666.....으로 가까워지는듯한 기분이 들죠? 실제로 그런지를 확인하기 위해서는 수열의 일반항을 구해야 하는데, 평범한 등차/등..

0. 들어가며 우선 정수론이 뭘까요? 수학의 한 분야라는 건 알겠는데, 정수를 다루는 걸까? 맞습니다. 정수들의 여러 성질들에 대해서 연구하는 학문입니다. 깊이 들어가면 현대 수학에서는 해석적 정수론이나 대수적 정수론적인 방법론으로 접근해서 문제를 푸는 경우가 아주 많고, 그렇기에 저 두 분야에 대한 간략한 이해도 상당히 필요하지만 우선은 수학 글이 아니라 PS 글이니까 이건 넘기도록 하겠습니다. 정말 간단하게 정수론에서 다루는 문제의 예시를 들면, 다음과 같은 것들이 있습니다. 어떤 수를 어떻게 하면 소인수분해를 빠르게 할 수 있는가? 어떤 수가 소수인 걸 어떻게 빠르게 알 수 있는가? 어떤 방정식의 정수 해들을 어떻게 빠르게 구할 수 있는가? 정말로 재미 없는 수학문제들 같아 보이지만, 정수론은 의외..