본문 바로가기

Problem Solving

(24)
First Solve 3개 퍼솔을 처음 시도해보았다. 쫄려서 쉬워보이는 것들만 찍먹함. ㅎㅎ
[BOJ 1167] 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다. 풀이 임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이..
[BOJ 12784] 인하니카 공화국 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제와 정확히 일치하는 문제를 GCC 출제 큐에 push하고 나서 반나절 뒤에 트리 디피 문제를 찾아 풀다가 우연히 발견했다. AC를 받기 전까지 제발 내 착각이기를 빌었다.. 흔한 유형이라 비슷한 문제가 있을 거라고 생각하기는 했지만, 아쉬운 것은 어쩔 수가 없다. 풀이 루트와 리프를 연결하는 경로가 없도록 만들 때, 자르는 간선의 가중치의 합이 최소가 되게 하는 문제다. 이는 dfs를 돌면서 트리의 정점에 대한 dp를 해결하면 된다. $dp[u]=\s..
자작 문제 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..