정보올림피아드 2004년 예선 초등 9번문제 풀이

오늘은 2004년 예선 문제를 풀어보겠습니다.

 

 

문제)

 

탁자 위에 각각 3L , 5L , 8L 를 담을 수 있는 물병이 있다. 

그런데 이 물병에는 눈금이 없어서 한 병 A에서 다른 병 B로 정량의 물을 옮기기 위해서는 A병이 비거나 B병이 찰 때까지 물을 부어야 한다. 

현재 8L 병에 물이 가득 담겨 있다고 할 때 이 물과 세 물병을 이용하여 정확히 4L 의 물을 얻고자 한다. 

최소 몇 번 물을 옮겨야 정확히 4L 의 물을 얻을 수 있을까? 단, 4L 의 물은 어느 물병에 담겨도 상관없다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

정답) 6회

 

풀이)

 

1회 8L->5L   담겨있는양(3L,5L,8L물병순) 0 - 5 - 3 

2회 5L->3L   담겨있는양(3L,5L,8L물병순) 3 - 2 - 3

3회 3L->8L   담겨있는양(3L,5L,8L물병순) 0 - 2 - 6

4회 5L->3L   담겨있는양(3L,5L,8L물병순) 2 - 0 - 6

5회 8L->5L   담겨있는양(3L,5L,8L물병순) 2 - 5 - 1

6회 5L->3L   담겨있는양(3L,5L,8L물병순) 3 - 4 - 1

 

이러한 문제는 컴퓨팅 사고력의 넓이우선 탐색에 해당하는 유형의 문제입니다.