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

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

그간 정말로 격조했다. 메이플스토리에 빠져서 며칠 간 헤어나오지를 못했다...! 이번 문제는 간단한 수학 문제다. 소수 판정과 관련된 약간 심화된 문제. 그러나 난이도는 그렇게 어렵지 않다. 비슷한 유형의 문제를 몇 풀어 봤다면 코드 복붙으로 일정 구간은 날로 먹을 수 있으니 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력 첫째 줄에 자연수 N(\(1 \le N \le 1\,000\,000\))이 주어진다. 예제 입력) 38 출력 첛째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 예제 출력) 5 7 1..

보자마자 풀이가 보이는 경우가 있다. 수학적 배경이 있으면 프로그래밍을 하는 데 하등 불편함이 없다는 말은 사실인 듯 하다. 이게 웰노운이 아니라서 다이나믹 프로그래밍으로 문제를 풀었다는 다른 사람의 기여를 보고 놀랐다. 하기사 다이나믹 프로그래밍이 점화식을 프로그램으로 푸는 제법 수월한 방법이기는 하지만... 여기서는 머리를 좀 써 보자. 그럼 본격적으로 풀이에 돌입해 보자. 문제 여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다. 각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때..