1부터 N까지 번호가 붙여진 N개의 마을과, 이들 마을을 모두 연결하는 N-1개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을로부터 다른 모든 마을까지 이들 도로들만 이용하여 갈 수 있다. 각 도로의 길이는 1이다.

이들 모든 마을에 있는 사람들의 안전을 보장하기 위하여 순찰대가 매일 모든 도로를 방 문하여야 한다. 경찰서는 마을 1에 있다. 그러므로 경찰관은 매일 마을 1에서 출발하여 마지막으로 마을 1로 돌아와야 한다.

8개의 마을로 구성된 아래의 예를 보자. 마을은 동그라미로 표시되어 있고, 경찰서가 있는 마을 1은 검은색 동그라미로 표시되어 있다. 마을을 연결하는 선분은 도로를 나타낸다. 순찰대가 매일 모든 도로를 방문하기 위하여, 순찰대가 방문해야 하는 전체거리는 14이다. 순찰대는 하루의 임무를 완성하기 위하여 각 도로를 2번만 방문해야 함에 유의하라.

순찰대가 모든 도로를 방문하는데 필요한 전체거리를 줄이기 위하여 이들 마을 사이에 K개의 지름길을 새로 만들기로 하였다. 각 지름길은 두 개의 마을을 연결한다. 두 지름길이 같은 마을에서 시작할 수 있다(아래 예 (c) 참고). 심지어 지름길이 루프일 수 있다; 즉 마을 자신을 연결할 수 있다.

예산이 제한되어 있으므로, K는 1 혹은 2이다. 또한, 돈이 쓸데없이 낭비되지 않도록 하기 위하여 순찰대는 하루에 각 지름길을 정확하게 한번 방문하여야 한다.

다음의 예를 보자.

예 (a)에서는 지름길 하나를 건설한 것으로 순찰대가 방문하는 도로의 전체 길이는 11이다. 예 (b)에서는 지름길 두 개를 건설한 것으로, 순찰대가 방문하는 도로의 전체 길이는 10이다. 예 (c)에서는 지름길을 두 개 건설하였는데 순찰대가 방문하는 도로의 전체 길이는 15이다. 이는 순찰대가 각 지름길을 정확하게 한번 지나가야 하는 조건 때문이다.

마을사이의 도로와 건설하여야 할 지름길의 수를 읽어 매일 순찰대가 방문하여야 하는 전체 거리를 최소하도록 하기위하여 지름길을 어디에 건설해야하는지를 구하는 프로그램을 작성하시오.

#2554 upload 50 done 8 how_to_reg 6

순찰 timer 1s memory - MB

#2554

순찰 1s - MB