게임 이론은 언제나 매우 힘들다. 근래 대회에서 게임 이론에 한 방 먹는 일이 계속 늘어가고 있다. 2023 연세대학교 프로그래밍 경진대회에서는 게임 이론 E를 건너뛰고 수학 F를 먼저 풀었고, 2024 MatKor w/s에서는 비록 다이아지만 게임 이론 한 문제를 못 풀어 2등과 3등이 갈렸다. 이게 연습으로 늘 만한 영역인지는 모르겠다. 잠 자기 전 랜디에서 보이는 게임 이론 문제가 튀어나와서 10분도 안 되어 바로 격파하긴 했지만 딱히 는 것 같지는 않다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 해적! 이는 멋진 직업인 것 같지만 큰 고충을 가지는 직업이다. 그 고충 중 하나는 많은 시간을 망망대해에서 지내야 한다는 점이다. 때때로 바람도 불지 않고, 하루종일 아무런 일도 없이 지나가는 날이 있..

1을 타패하고 33을 또이쯔로 쓰겠다. 며칠 전 대회인 제4회 MatKor의 H번 문제이다. 총 16문제짜리 셋이었으니, 이 뒤로 이것보다 어려운 문제가 8개나 있다는 뜻이다. 이 문제 난이도도 절대 만만하지 않다! 본대회에서 식 정리하는 데만 20분을 넘게 썼다. 내 영역이라서 그나마 빠르게 풀기는 했는데, 그 빠르게 푼다는 게 40분 조금 넘게 걸렸던 문제다. 쏟은 시간 보고 제법 만만치 않으리라고 생각했는데 설마 Platinum I이었을 줄은... 그럼 본격적으로 풀이에 돌입해 보자. 문제 2024년 3월 9일 제4회 MatKor Cup이 개최된다. 이번 MatKor Cup에는 총 \(n\)명이 참가했고, 각 참가자는 \(1\)번부터 \(n\)번까지의 번호가 붙어있다. 이번 대회 운영진인 준혁이는 ..

난 세그먼트 트리를 모른다. 그런데 어느 날 balbad.ac solved.ac의 태그를 보다 보니 내가 세그먼트 트리 태그가 달린 문제를 푼 게 아닌가. 그것도 두 문제나. 이것은 기여가 잘못되었거나 아니면 비슷한 난이도의 다른 풀이가 있거나 둘 중 하나. 아니나 다를까 세그먼트 트리를 전혀 쓰지 않는 풀이법이 있었다. 대신 일정 이상의 수학 지식과 직관력이 요구되는 문제였다. 젠장 또 수학 문제야. 나는 수학 문제를 보고 말았어. 이제 나는 수학 문제를 풀어야만 해... 아무튼. 그럼 본격적으로 풀이에 돌입해 보자. 문제 상근이는 빵집에서 일한다. 상근이의 퇴근하기 전에 하는 마지막 업무는 빵을 사장이 원하는 순서대로 정렬하는 것이다. 최근에 상근이는 선영이에게 신기한 기술을 하나 배웠다. 이제 상근..

어제 수학 레이팅을 올리겠다고 앉은 자리에서 Platinum 수학 문제 두 개를 풀었다. 아뿔싸. Platinum 4부터 레이팅을 올려 준다고 한다. 그냥 Platinum을 두 개 푼 사람이 되어 버렸다. 이 문제는 그 두 문제 중 하나이다. 앉은 자리에서 푸는 데 20분도 걸리지 않았으면 구현은 그렇게 빡세지 않다는 이야기이다. 아이디어가 메인인 문제. 그럼 본격적으로 풀이에 돌입해 보자. 문제 \(\text{dig}\)라는 함수를 다음과 같이 정의하자. $$\text{dig}(x) = x\,\,\,\,(0 \le x \le 9)$$ $$\text{dig}(x) = \text{dig}(\text{x의 모든 자리수의 합})\,\,\,\,(x \ge 10)$$ 예를 들어, \(\text{dig}(49) =..

밀러-라빈과 폴라드-로 알고리즘을 같이 쓰는 경우가 많아서 간과하는 경우는 많지만, 밀러-라빈 하나만으로도 이미 충분히 쓸모가 있는 알고리즘이다. 그도 그럴 것이, 어떤 수가 소수인지 아닌지 로그 시간만에 판별 가능한 알고리즘이 그렇게 적지는 않다! 밀러-라빈 단독으로 사용하는 대표적인 문제 중 하나가 바로 이 문제이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy+x+y이다. (x와 y는 양의 정수) 동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다. 동규..

사실 이건 제법 쟁여두려고 했으나... 작성자 본인이 처음 푼 플래티넘 V 이상 문제이기도 하고, 며칠 간 고민하다 겨우 푼 문제라 그런가 감회가 새롭기도 하다 게다가 이미 방법론은 다른 경로로 알고 있어서 더욱. 그래서 오늘의 문제로 11402번 문제를 택하기도 했다. 열화판으로 11401번 문제가 있는데, 접근 방식은 아예 다르니 조심하길. 잡설이 길었다! 그럼 본격적으로 풀이에 돌입해 보자. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, K와 M이 주어진다. (1 ≤ N ≤ \(10^{18}\), 0 ≤ K ≤ N, 2 ≤ M ≤ 2000, M은 소수) 예제 입력) # 예제 입력 1 5 2..