재창김과의 싸움에서 승리한 성민류는, 흥분한 마음을 가라앉히고 탐구관 문손잡이를 잡았다.
그런데, 방송 스피커로 익숙한 목소리가 흘러나왔다.
"지구과학 올림피아드 지학실로 옵니다~".
이럴수가, 지올에 나가는 성민류는 꼼짝없이 지학실로 이송될 위기에 처했다.
지금 지학실에 갇힌다면, 1년동안 지학실에서 합숙교육을 받게 되는데, 그러면 3학년인 S는 대학교로 가버릴것이다.
성민류는 굉장히 기발한 생각을 해냈는데, 바로 지학실을 폭파시켜 합숙교육을 미루는 것이다.
탐구관 화장실에 폭탄이 숨겨져 있다는 전설을 듣고, 성민류는 화장실에서 폭탄을 획득하였다.
폭탄이 좀 이상하게 생겼는데, 다음 그림은 폭탄의 모양 예시이다.
불 모양은 는 도화선에 불을 붙이는 곳, 폭탄 모양은 폭탄의 위치, 선은 도화선이다.
문제를 위해 각 연결점마다 초록색으로 번호를 붙일 것이다. 이때, 1번은 불을 붙이는 점이다.
번호를 붙이는 방법은 다음 그림의 연두색 선을 보고 이해하라. 검정 숫자는 도화선의 길이이다.
S점에 불을 붙인 후, 불이 도화선을 따라가는 속도는 항상 일정하다.
즉, 5-5-3으로 연결된 폭탄은 5-8-3으로 연결된 폭탄보다 빨리 터지고, 5-4-3-1로 연결된 폭탄과 같이 터진다.
환진윤 선생님께서 최신 방공호 설계법으로 지학실을 리모델링하셨기 때문에, 모든 폭탄이 동시에 터지지 않는 이상 지학실은 안전하다.
그래서 성민류는 모든 폭탄이 동시에 터지도록 도화선의 길이를 손보려고 한다.
예를들어,
이렇게말이다.
도화선의 길이를 1 변경하는데는 1의 노력이 든다.
즉, 위 그림과 같이 변경하면 6의 노력이 든다.
게으른 성민류는 최소한의 노력으로 도화선을 손보려고 한다.
폭탄의 상태를 입력받아, 최소한의 노력이 얼마인지 출력해보자.
참고 : 도화선의 길이를 0으로 줄여도 된다.