Need not to know

▣ 문제 출처 ─ 2017년도 한국 정보올림피아드(KOI) 전국 본선 고등부 1번 문제 ▣ 알고리즘 분류 ─ BFS / 수학 / 구현 ▣ solved.ac 기준 난이도 ─ Gold II 2017년도 고등 KOI 1번으로 나온 문제다. (문제의 내용은 여기에서 확인할 수 있다.) 문제의 내용을 대략 요약하면 다음과 같다: 용량이 다른 두 개의 빈 물통 A, B가 있고, 각 시행마다 하나의 물통을 가득 채우거나, 비우거나, 한 물통에서 다른 물통으로 물을 옮기는 행위를 할 수 있다고 한다. 물통 A, B의 용량 $a,\, b\,(a < b)$와 최종 상태 $(c,\, d)$가 주어질 때, $(0,\, 0)$에서 $(c,\, d)$로 만들기 위한 최소 시행 수를 구하는 문제다. 만약 최종 상태로 만들 수 없다..