PS 이야기

1. 물통 (bucket) 크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다. 1) 크기가 A인 물통을 비우거나 가득 채운다. 2) 크기가 B인 물통을 비우거나 가득 채운다. 3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다. 4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다. 크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나..