리유나의 항해일지

(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가 주어졌을 때 두 건물 사이의 거리를 ..

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

900솔브를 달성했습니다! 시험기간 버프가 크게 작용한 것 같네요 ㅋㅋ... 구체적으로는 역시 꿀문제 헌팅이랑... 플로우 컵 문제 쭉 돌았는데(뭐 이런 구데기가 다 있나 전부 KMO 기하잖아)그래도 900번째 문제는 조금 의미있게 하고 싶어서 다이아 문제로 했습니다. 900솔브는 다이아 5 문제로 했는데 간단한 아이디어는 (3+sqrt(5))^n+(3-sqrt(5))^n이 항상 정수임을 수학적 귀납법으로 증명할 수 있습니다. 이 트릭을 알고 있으면 난이도가 순식간에 거의 실버급으로 떨어지는 문제라고 생각합니다... 저거 풀고 같은 문제 하나 있길래 또 풀고 왔습니다. https://www.acmicpc.net/problem/12925 12925번: Numbers 각 Test case에 대해, “Case..

뜬금없이 이런 카테고리의 글을 올리게 된 이유는, 제가 지금 고3학생을 과외하고 있는 탓이 큽니다. 아마도 여유가 생기는대로 21번, 29번, 30번 풀이도 올릴 수 있을 것 같습니다. 이번 9월 모의고사가 여러모로 신기한 부분이 많았는데, 21번이 미적이 아니었던 것도 그렇고, 30번도 뭔가 새로운 유형이었던 게 신선했습니다. 그리고 15번 언저리에 이정도 난이도의 문제가 나온 것도 조금 신선했네요... 개인적으로 19번 정도는 가도 되지 않았나 싶습니다. 언뜻 보기에는 대충 좌표 잘 잡아서 풀면 될 것 같아 보이지만, 사실 그냥 그렇게 풀기에는 조금 힘든 문제였습니다. 이 문제에서 핵심은 $$y=e^x$$ 그래프를 시계 방향으로 90도 회전시키면 y=-lnx 그래프가 나온다는 점이라고 할 수 있습니다..

2001년 ACM ICPC 예선으로 나왔던 문제입니다. 문제는 여기서 확인할 수 있습니다. 고등학교 2학년 때였나, 특이한 정보과학 과목을 수강했던 적이 있었습니다. 선생님께서 마지막에 문제 24개를 주시면서 여기서 95% 이상을 풀면 시험 성적에 관계없이 A+을 주겠다고 하셨던 적이 있는데, 그 중 한 문제로 처음 접했던 기억이 납니다. 처음에 이 문제를 봤을 때는 DP(동적계획)와 같은 방법을 사용해서 재귀적으로 풀어야 하나 하고 고민했지만, 이런 시도가 언제나 그렇듯이 잘 되질 않았습니다. Brute Force(완전탐색)으로 해볼까도 생각해봤는데, 아무래도 m+n이 10 이상 30 미만인데 30이면 전체 가능한 경우의 수가 2^30(≒10^9)정도로 조금 무리인 감이 있습니다.(게다가 저게 되는지 ..