정올이는 탐험가가 되어 포션을 모으려 한다. 맵은 N개의 방으로 이루어져 있으며, 1번부터 N번까지 번호가 매겨져 있다. 이 방들은 N-1개의 간선으로 연결되어 있으며, 트리 형태를 이룬다.

정올이는 "탐험"이라는 일련의 행동을 통해 맵을 탐험할 수 있다. 탐험은 트리에서 방 1에서 시작하여 다른 방으로 이동하는 단순 경로이다. 한 번의 탐험을 마치면 다시 방 1에서 새로운 탐험을 시작할 수 있다. 모든 방을 최소한 한 번 방문하여 맵을 완성하는 것이 목표이며, 이때 필요한 탐험의 횟수를 최소화해야 한다.

부차적인 목표는 가능한 한 많은 포션을 모으는 것이다. 매 회차의 탐험에 포션은 맵의 특정 방에 나타나며, 해당 탐험에서 포션이 나타난 방을 방문하면 포션을 획득할 수 있다. 만약 포션을 획득하지 못하면 해당 탐험이 끝날 때 포션이 사라져 이후 탐험에서는 획득할 수 없다.

정올이는 똑똑한 프로그래머로서 게임 파일을 살펴본 결과, 다음 N번의 탐험 전에 포션이 어디에 나타날지 알아낼 수 있었다. 맵을 최소 탐험 횟수로 완성할 때, 맵에서 최대한 모을 수 있는 포션의 개수는 얼마인가?

#6217 upload 5 done 2 how_to_reg 2 call_split Subtarea

탐험가 정올이 timer 2s memory 1024MB

#6217
Subtarea

탐험가 정올이 2s 1024MB