Need not to know

▣ 문제 출처 ─ 제3회 kriiicon ㅅ번 문제 ▣ 알고리즘 분류 ─ 수학 / 구현 / 기하 / 많은 조건 분기 / 미적분학(그린 정리) ▣ solved.ac 기준 난이도 ─ Ruby II 문제 링크: https://www.acmicpc.net/problem/11392 약 한 달 전쯤, 모 세미나(?)에서 본 문제의 풀이에 대해 발표할 일이 있었어서 발표 자료를 만들었는데… 나름대로 열심히 만든 자료를 한 번 발표하는 데 쓰고 끝내기는 좀 아까워서 여기에도 올려봅니다! (파일 저장 후 '읽기 전용'으로 여시면 됩니다.) 원본 발표 자료에서 개인 정보나 문제 풀이와 관련 없는 부분 등을 조금 수정한 버전입니다. 이 문제를 도전하시는 분들에게 조금이라도 도움이 되셨으면 좋겠습니다. :) 덧붙여, 본 문제..

▣ 문제 출처 ─ 제1 회 곰곰컵 G번 문제 ▣ 알고리즘 분류 ─ 수학 / 확률론(기댓값의 선형성) / 조합론(더블 카운팅) ▣ solved.ac 기준 난이도 ─ Gold II (개인적으로는 골1 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/25197 $N$명의 사람들이 서로 다른 $K$개의 조에 균등한 확률로 랜덤하게 나뉘어 들어간다. 각 조에서 모든 쌍이 식사를 한 번씩 한다고 할 때, 전체 식사 횟수의 기댓값은 얼마일까? 일단 $N$명의 사람들이 $K$개의 조에 들어가는 모든 경우의 수는 $K^N$가지인 걸 알고 있으므로 총 식사 횟수의 합을 구할 수 있으면 되는데, 모든 경우에 대해 일일이 식사 횟수를 구하는 건 범위상 당연히 불가능하다. 그런데 어차..

※ 앞으로 몇 개의 게시글에 걸쳐, 비슷한 주제로 글을 쓸 예정입니다. ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다.1. 뫼비우스 함수와 디리클레 합성곱 (현재 글)2. Double Counting과 Harmonic Lemma3. 곱셈적 함수 테이블 만들기4. Mertens Trick (xudyh's sieve) Preliminaries and Notations  정수론에서 다루는 대상 중 수론적 함수(산술적 함수, Arithmetic Function)라는 것이 있다. 모든 양의 정수에 대해 정의된 복소함수를 일컫는데, 쉽게 말해서 수열을 의미한다. 그리고 수론적 함수 중에서도 조금 더 특별한 아이들을 모아 따로 부르는 명칭이 있으니, 그것이 바로 곱셈적 함수(Multiplicative Func..

▣ 문제 출처 ─ 2017년도 한국 정보올림피아드(KOI) 전국 본선 고등부 1번 문제 ▣ 알고리즘 분류 ─ BFS / 수학 / 구현 ▣ solved.ac 기준 난이도 ─ Gold II 2017년도 고등 KOI 1번으로 나온 문제다. (문제의 내용은 여기에서 확인할 수 있다.) 문제의 내용을 대략 요약하면 다음과 같다: 용량이 다른 두 개의 빈 물통 A, B가 있고, 각 시행마다 하나의 물통을 가득 채우거나, 비우거나, 한 물통에서 다른 물통으로 물을 옮기는 행위를 할 수 있다고 한다. 물통 A, B의 용량 $a,\, b\,(a < b)$와 최종 상태 $(c,\, d)$가 주어질 때, $(0,\, 0)$에서 $(c,\, d)$로 만들기 위한 최소 시행 수를 구하는 문제다. 만약 최종 상태로 만들 수 없다..