두 개의 양동이

지침

크기가 서로 다른 양동이 두 개와, 어느 양동이를 먼저 채울지가 주어졌을 때, 양동이 사이로 물을 전략적으로 옮겨 정확한 리터 수를 측정하는 데 필요한 동작 횟수를 구하세요.

풀이가 따라야 하는 규칙이 몇 가지 있어요:

• 한 번에 한 가지 동작만 할 수 있어요.
• 가능한 동작은 세 가지뿐이에요:
  1. 한 양동이의 물을 다른 양동이에 붓기. 다음 중 하나가 될 때까지 해요: a) 첫 번째 양동이가 비었을 때 b) 두 번째 양동이가 가득 찼을 때
  2. 양동이 하나를 비우고 다른 양동이는 그대로 두기.
  3. 양동이 하나를 채우고 다른 양동이는 그대로 두기.
• 동작을 한 뒤에는 시작 양동이가 비어 있고 다른 양동이가 가득 찬 상태가 되면 안 돼요.

프로그램은 다음을 입력으로 받아요:

• 첫 번째 양동이의 크기
• 두 번째 양동이의 크기
• 도달해야 하는 원하는 리터 수
• 어느 양동이를 먼저 채울지, 즉 one 양동이 또는 two 양동이

프로그램은 다음을 구해야 해요:

• 시작 양동이를 처음 채우는 것을 포함해, 원하는 리터 수에 도달하는 데 필요한 총 동작 횟수
• 원하는 리터 수가 담기게 되는 양동이, 즉 one 양동이 또는 two 양동이
• 다른 양동이에 남아 있는 리터 수

참고: 양동이 하나에 변화가 생기든 둘 모두에 변화가 생기든, 그때마다 동작 한 번(1회)으로 쳐요.

예시: one 양동이에는 최대 7리터, two 양동이에는 최대 11리터를 담을 수 있어요. 어떤 단계에서 one 양동이에 7리터, two 양동이에 8리터가 들어 있다고 해봐요 (7,8). one 양동이를 비우고 two 양동이는 그대로 두어 각각 0리터와 8리터가 남는다면 (0,8), 이는 동작 한 번으로 쳐요. 반대로, two 양동이가 가득 찰 때까지 one 양동이에서 two 양동이로 물을 부어 one 양동이에 4리터, two 양동이에 11리터가 되었다면 (4,11), 이것도 동작 한 번으로만 쳐요.

또 다른 예시: one 양동이에는 3리터, two 양동이에는 최대 5리터를 담을 수 있어요. one 양동이부터 시작해야 한다고 해봐요. 그러면 첫 번째 동작은 one 양동이를 채우는 거예요. 두 번째 동작으로는 one 양동이를 비우기로 해요. 세 번째 동작으로는 two 양동이를 채우면 안 돼요. 세 번째 규칙을 어기게 되거든요. 어떤 동작을 한 뒤에도 시작 양동이가 비어 있고 다른 양동이가 가득 찬 상태가 되면 안 되니까요.

Lindsay Levine이 Fullstack Academy에서 <3를 담아 작성했어요.

---

출처

물 붓기 문제