강아지 모으기

그림과 같이 여섯 마리의 강아지가 한 섬에 한 마리씩 있다. 그림에서 화살표는 섬과 섬 사이를 오갈 수 있는 뱃길이며 각 숫자는 이동에 필요한 연료의 양을 나타낸다. 배도 여섯 척이 있어 섬마다 한 척씩 대기하고 있다. 모든 배는 한 번에 최대 다섯 마리를 태울 수 있을 만큼 크다.

오랜만에 여섯 마리의 강아지들을 서로 만나게 해주려고 한 섬으로 모으려고 한다. 이때 필요한 연료의 양의 최솟값은?

문제 형식

객관식

출처

• KOI 2022 1차대회 중등부 1교시 4번