본문 바로가기

Problem Solving

(27)
[BOJ 12784] 인하니카 공화국 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수 없다. 풀이 루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다. 이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다. $dp[u]=\su..
자작 문제 1. 영단어 외우기 문제 영어 단어 시험이 사흘 앞으로 다가왔다. 모두가 바쁘게 단어를 암기하고 있는 와중에 GCC 출제 아이디어를 고민하고 있는 희원이는 두 마리 토끼를 다 잡을 수 있는 묘안을 떠올렸는데, 그것은 바로 영단어를 숫자로 바꿔서 암기하는 것이었다..! a, b, c, ... , z 를 각각 0, 1, 2, ..., 25 에 대응시켜 26진법인 영단어를 10진법의 수로 변환하여 외우고 시험을 볼 때 10진법의 수를 영단어로 다시 변환할 수만 있다면, 수행평가 만점은 따놓은 당상이나 마찬가지다. 영단어 또는 변환된 수와 영단어의 길이가 주어질 때, 이를 변환하거나 다시 영단어로 만들어 희원이의 수행평가를 도와주자! 입력 첫째 줄에 길이가 23 이하이고 소문자 알파벳으로만 이루어진 영단어, 또..
[BOJ 16998] It’s a Mod, Mod, Mod, Mod World 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net 풀이가 적혀있던 노트를 겨우 찾아서 포스팅한다. ㅎㅎ ㅠ 풀이 $x\%m=x-(x/m)*m$ 임을 이용해 주어진 식을 변형하면 $ans=\frac{n(n+1)}{2}p-q\sum_{i=1}^{n}\le..
Ruby V 실력은 Diamond V..
Class 9 수준 높고 멋진 셋이지만 이 이상은 풀 엄두가 안 난다.. 나는 16998번 「It's a Mod, Mod, Mod World」를 가장 재밌게 풀었다. 정말 오래전부터 고민했던 문제인데, 8483번을 풀고 나니 쉽더라 :)