리유나의 항해일지

문제 링크는 이쪽입니다. 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.....으로 가까워지는듯한 기분이 들죠? 실제로 그런지를 확인하기 위해서는 수열의 일반항을 구해야 하는데, 평범한 등차/등..

(2022년의 마무리를 맞아서) 2022번 사다리라는 문제를 풀었습니다. 난이도는 솔브드 기준 골드 5고, 실제로(제 기준)그리 어려운 문제는 아니지만 적당히 접근하는 방법과 풀이가 problem solving과 단순 기하학/수학이 잘 접목되어서 이루어지는 느낌이라 꽤 괜찮은 수학 문제라고 생각했습니다. 문제 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 문제 자체는 아주 간단합니다. 위 그림에서 x, y, c가 주어졌을 때 두 건물 사이의 거리를 ..

너무나도 감개무량하네요. 이걸 달 수 있을거라곤 전혀 생각 못하고 살았어요. 이 과정에서 편식하던 알고리즘들 이것저것 많이 먹게 되어서 좋았다고 생각해요. 다만 아직도 트리 같은 걸 너무나도 편식하는 것 같아서 조금 걱정이네요. 클래스 8 가는 길에 풀었던 문제들은 다음과 같습니다! 몇개 빼고 거의다 수학/기하학/게임이론 쪽이네요 ㅋㅋㅋ; 앞으로 두루두루 여러 분야의 문제들을 풀면서 연습해보겠습니다!

https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 정말로 유명한 문제입니다. 당시 중등부에 이정도 난이도 문제가 나와서 말이 많았다고도 하고, 풀이 자체는 여러 문제에서 유용하게 쓰일 수 있기 때문에 세그트리 응용을 공부할 때 꼭 한번씩은 짚고 넘어가는 문제입니다. 이 문제의 프리퀄 격이라 할 수 있는 연속합과 쿼리(예전에 쓴 블로그 글)를 풀어보신적이 있으시다면 더욱 이해가 쉬울 것입니다. 문제를 요약하면, "..