오늘 내가 몸담은 동아리 모르고리즘에서 월례 대회가 열렸다. 골드 이하로 다양한 태그의 교육적이고 인기 없는 문제 셋을 구성한다는 쉽지 않은 과제였을 텐데 역시 운영진이 모두 엄청난 실력과 선구안을 지닌 사람들이라 그런지 이대로 대회에 나와도 크게 손색 없을 법한 셋이 탄생되었다. 실력 없는 물로켓인 내가 풀기에 딱 알맞은 셋이었다. 아쉽게 좌셋은 아니었지만. 이 문제는 태그 덮고 난이도 덮고 풀었을 때는 마지막에 시간이 모자라서 못 풀었고, 이후 풀이 설명하는 시간에 내 풀이를 말로 설명하고 해설자인 Serendipity__의 말에 힌트까지 얻어 집에서 완성해 냈다. 중간에 IndexError가 자꾸 났는데, 0부터 3000까지 키를 가지는 배열의 길이를 3001이 아니라 3000으로 저장하는 치명적인..

오랜만에 문제 풀이 포스트를 올려 본다. 근래 검수다 뭐다 해서 바빴고, 검수하던 대회가 개최되자마자 신학기에 금요일과 토요일은 MatKor 온사이트 대회까지 있었다. 거의 모든 일정이 종료되고 나서야 이렇게 짬이 생긴 것 같다. 짬내서 쓰지 않으면 이제 시간도 잘 안 나는 듯 하고... 달려 있던 태그가 많은 조건 분기인데, 난 그런 거 귀찮아서 무작위화로 풀었다. 사실 조건 분기를 어떻게 해야 할지 감이 잡히기도 전에 무작위화 풀이가 생각이 난 게 크다. 그럼 본격적으로 풀이에 돌입해 보자. 의역이 좀 많다. 문제 Ett vanligt magitrick går till på följande vis: 다음과 같은 숫자 마술을 생각해 보자. Tänk på ett tal. Subtrahera 1 från ..

사실 이번 게시글은 자기성찰성이 깊은 게시글이다. 수학 원툴에서 쓸 수 있는 도구를 다변화시킬 필요가 있어서 우선 dp를 연습하기로 하고 골드 범위 내에서 랜덤으로 뽑기를 반복했는데, dp 문제임을 알고 있어도 dp로 못 접근한 문제가 있기 때문이다. 이게 그렇고, 다른 것도 하나 있는데... 하여튼 생각해보다가 안 되니 아득하게 높은 레벨의 풀이를 정말 억지로 끌고 와서 겨우겨우 풀어냈다. 닭 잡는 데 핵폭탄을 떨어트린 느낌이라고 해야 하나... 그럼 본격적으로 풀이에 돌입해 보자. 문제 양의 정수 \(N\) \((1\le N\le 2000)\)을 서로 다른 자연수의 합으로 나타내는 방법은 여러 가지가 있다. 예를 들어, \(N=5\)인 경우 \(N=5=2+3=1+4\)로 총 3가지 방법이 있다. \(..

정말로 그간 격조했다. 반쯤 블로그를 유기한 것 같은데... 현생이 너무 바빴다. 방학 때 이 블로그를 조금 더 많이 충실하게 만들 생각이다. 이번 문제는 ICPC 북서유럽 리저널인 SWERC 2015 C번 문제다. 서강대학교 PS 학회와 연합 팀연습을 했을 때 다 같이 시원하게 말린 다음 내 아이디어로 푼 문제다. (자랑 맞다.) 발상의 전환이 필요한 문제다. 이런 문제가 아니었으면 내 아이디어가 튀어나오기 전에 괴물 팀원이 구현을 끝내 놓으신다. 나는 우리 동아리 코딩 최약체다. ICPC 리저널답게 영어로 된 문제다. 처음에는 내가 직접 번역하다가 영 귀찮아서 DeepL의 초고를 보고 내가 덧대는 방식으로 번역하기로 했다. 난 영어도 잘 못하는데... 그럼 본격적으로 풀이에 돌입해 보자. 문제 Aft..

넓은 분야의 수학 문제를 이것저것 얕게 손대다 보면 본의 아니게 잡지식이 늘게 된다. 부호를 보존하는 제곱을 계산하는 방법이라거나, 쓸데없는 계산을 우회해서 계산하는 경우의 수를 비약적으로 줄인다거나. 런타임 전의 전처리에 가까운 분야이기는 하지만, 하여튼 그러하다. 이번 문제는 2월 26일에 개최된 제1회 흐즈로컵 C번 문제이다. 나는 실수하기는 쉬우나 그렇게 어려운 문제는 아니라고 보았는데, 다른 사람들은 그렇지 않다 생각했나 보다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 흐즈로는 현재 2차원 좌표평면에서 \((x,y)\)에 위치한 전망대에 있습니다. 전망대 주변에는 \(n\)개의 과녁이 존재합니다. 각각의 과녁은 크기가 없는 점으로 취급합니다. 흐즈로는 공을 던져서 과녁을 맞추고자 합니다. 이 ..

각종 프로젝트로 인생이 바빠져서 블로그 관리를 전혀 하지 못했다. 복수전공 승인, 수강신청, 동아리 활동, SUAPC 출전... 이제 막 100일을 찍은 초보 코더의 삶에 이리 많은 일이 벌어질 줄이야. 오랜만에 귀엽고(?) 재미있는 수학 문제를 발견했다. 인터넷에 풀이도 거의 없더라. 난이도만큼의 값을 하지만, 배경지식이 없으면 난항에 빠질 것 같은 문제다. 풀이방법이 각양각색이지만, 이 포스트에 적혀 있는 풀이는 내가 이 문제를 보자마자 생각해낸 풀이인 이분 탐색 + 스털링 근사가 될 것이다. 숏코딩을 보니 기상천외한 naive 풀이도 있더라. 발상을 어떻게 했는지 궁금하다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 양의 정수 n이 주어졌을 때 n의 팩토리얼인 n!을 구하는 것은 쉽다. 이번에는 n..