지침
크기가 서로 다른 양동이 두 개와, 어느 양동이를 먼저 채울지가 주어졌을 때, 양동이 사이로 물을 전략적으로 옮겨 정확한 리터 수를 측정하는 데 필요한 동작 횟수를 구하세요.
풀이가 따라야 하는 규칙이 몇 가지 있어요:
- 한 번에 한 가지 동작만 할 수 있어요.
- 가능한 동작은 세 가지뿐이에요:
- 한 양동이의 물을 다른 양동이에 붓기. 다음 중 하나가 될 때까지 해요:
a) 첫 번째 양동이가 비었을 때
b) 두 번째 양동이가 가득 찼을 때
- 양동이 하나를 비우고 다른 양동이는 그대로 두기.
- 양동이 하나를 채우고 다른 양동이는 그대로 두기.
- 동작을 한 뒤에는 시작 양동이가 비어 있고 다른 양동이가 가득 찬 상태가 되면 안 돼요.
프로그램은 다음을 입력으로 받아요:
- 첫 번째 양동이의 크기
- 두 번째 양동이의 크기
- 도달해야 하는 원하는 리터 수
- 어느 양동이를 먼저 채울지, 즉 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를 담아 작성했어요.
출력 형식
solve() 메서드는 다음 속성을 가진 객체를 반환해야 해요.
-
moves - 목표에 도달하는 데 필요한 양동이 동작 수
(시작 양동이를 채우는 것도 포함해요),
-
goalBucket - 목표 양에 도달한 양동이의 이름,
-
otherBucket - 다른 양동이에 들어 있는 양.
예:
{
"moves": 5,
"goalBucket": "one",
"otherBucket": 2
}
