[고등부] 2024 KOI 1차대회 대비 모의고사 (1주차)

1번부터 N번까지 번호가 매겨져 있는 N개의 도시는 각각 전투력을 갖고 있으며,

서로 다른 두 도시를 양방향으로 잇는 N-1개의 도로가 있어 도로를 따라 도시 간 이동이 가능하다.

각 도시들을 묶어 하나의 나라로 간주하여 위, 촉, 오, 세 국가를 만들어 전쟁 시뮬레이션을 진행하려고 한다.

각 국가는 적어도 하나의 도시를 포함해야 하며 각 도시는 정확히 하나의 국가에 포함되어야 한다.

또한, 다른 국가의 도시를 거치지 않으면서 도로를 따라 국가 내 임의의 도시 간 이동이 가능해야 한다.

어떤 국가가 지나치게 강력하여 쉽게 삼국을 통일하면 제갈량의 천하삼분지계가 실패하기에 전투력을 최대한 균형 있게 분배하는 것이 중요하다.

국가의 전투력은 국가에 포함된 모든 도시의 전투력의 합으로 정의된다.

고민 끝에 당신은 세 국가의 전투력을 각각 a,b,c라 할 때,

\left|a-b \right| + \left|b-c \right| + \left|c-a \right|를 최소로 하는 것이 전투력을 균형 있게 분배하는 방법이라고 결론 지었다.

삼국의 전투력을 균형 있게 분배하시오.