Redddy's Devlog

🔈 문제 두더지가 정보섬에 올라왔다! 두더지는 정보섬 지하에 여러 채의 자택을 소유하고 있다. 두더지는 집 사이를 오가는 걸 좋아한다. 정보섬에는 총 N개의 두더지 집이 있으며 이 집들은 N-1개의 길로 연결되어 있다. 임의의 집에서 또 다른 집으로 가는 경로는 항상 유일하게 하나만 존재한다. 즉, 두더지 집들은 트리 형태로 모두 연결되어 있다. 어떤 길을 지날 때, 두더지는 W만큼의 만족도를 얻는다. 어느 날, 아래의 그림과 같은 집을 가진 두더지는 집1에서 집4로 이동했다. 이때 거치게 되는 집은 (1 → 2 → 3 → 4)이다. 두더지는 한 번 이동할 때마다, 이동경로에 포함되는 만족도들 중에서 가장 최소인 만족도를 얻는다. 즉, (1 → 4)의 경우에는 만족도를 2만큼, (6 → 2)의 경우에는 ..

🔈 문제 BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다. 현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠..