23575 Squid Game

https://www.acmicpc.net/problem/23575

물통 1, 2, 3에 각각 물이 리터 들어있다. 에 대해, 리터의 물이 들어있는 물통 와 리터의 물이 들어있는 물통 을 선택하여, 물통 에 리터, 물통 에 리터의 물이 남도록 물통 에서 물통 로 물을 붓는 동작을 할 수 있다. 처음 물의 양 가 주어졌을 때, 1000번 이내의 동작으로 한 물통을 완전히 비우도록 하는 동작을 순서대로 출력하라. 물통 에서 물통 로 물을 붓는 동작을 와 같은 꼴로, 각 동작마다 개행하여 출력하면 된다.

아이디어

목표는 매 동작을 잘 조합해서 물통에 든 물의 최솟값을 줄이는 것이다. “최솟값을 두 배 정도 줄일 수 있는 동작 묶음”을 만들 수 있다면, 이므로 대략 30번 반복을 통해 최솟값을 0으로 만들 수 있다.

풀이

• 물을 붓는 동작을 사용하여 나머지 연산을 구현하였다.
• 최대 30번 정도의 동작을 통해 에 대해 리터의 물이 담긴 물통으로부터 리터 또는 리터의 물이 남은 물통을 만드는 동작 묶음을 구성한다. (는 가 음이 아닌 정수가 되도록 하는 임의의 수이다.)
• 에 따라 둘 중 하나를 선택하여 최솟값을 절반 수준으로 줄일 수 있다.
• 이 동작 묶음이 많아야 30번 정도 시행되므로 1000회 이내 제한을 만족한다.

동작 묶음 구성

매 동작 묶음을 시작할 때, 물통에 든 물의 양이 각각 리터라고 하자. 물통 1, 2, 3에 각각 물이 리터 들었을 때, 이도록 물통의 번호를 잘 바꾸자. 이때 이거나 이면 운 좋게 답을 얻을 수 있다. 운이 좋지 않은 경우를 위해 를 가정하자.

라고 하자. 다음으로 물통에 남은 물의 양 중 최솟값이 리터 또는 리터 이하가 되도록 만들 것이다. 라고 하자. 이므로 이다. 인 경우를 예시로 들어 어떤 전략을 취하여야 할지 생각하여 볼 것이다.

• 인 경우, 은 보다 작거나 같다. 이 경우에는 물통 2에서 물통 1로 물을 부었을 때 물통 2에 물이 리터 남는다.
• 인 경우, 는 보다 작거나 같다. 이 경우에는 물통 3에서 물통 1로 물을 부은 후, 물통 1에서 물통 2로 물을 부었을 때 물통 1에 물이 리터 남는다.

각 경우는 과 를 비교하여 구별할 수 있다. 인 경우에 비슷한 결과를 만들 수 있는지 탐색하자.

우선, 이 보다 작거나 같다고 가정하자.

• 일 때, 물통 3에서 물통 1으로 물을 부을 것이다. 물통 1, 2에 각각 물이 리터 남는데, 이다.
• 일 때, 물통 2에서 물통 1으로 물을 부을 것이다. 물통 1, 2에 각각 물이 리터 남는데, 이다.

위 과정 이후 에 를 대입하고, 인 동안 위 과정을 반복한다. 이 되었을 때 전술한 동작을 통해 물통 2에 물을 리터 남길 수 있다.

이 지점에서 문제가 될 수 있는 것은 물통 3에서 물통 1으로 항상 물을 옮길 수 있느냐 하는 것이다. 그러나 이는 조건만으로 충분하다. 위의 반복이 진행되면서 물통 1에 남는 물의 양은 으로 두 배씩 늘어나고, 일 때, 즉 일 때 중단된다. 는 이다. 마지막 단계에서 물통 3에서 물통 1로 물을 붓지 않을 것이고, 단계에서 물통 3에서 물통 1로 붓는 물의 양은 이다. 옮겨지는 물의 양은 많아야 이고, 이므로, 물통 3으로부터 항상 물을 옮길 수 있다.

이 보다 크다고 가정하자. 새로운 과정을 소개하기 전에, 위 과정을 분석하여 보자. 위 과정은 물통 2에 리터를 남기게 된다. 이 과정은 다음과 같이 요약할 수 있다:

• 두 물통의 물 차이가 리터가 될 때까지 물을 잘 옮긴다.
• 마지막 동작을 통해 차이를 실현한다.

그러니 이번에는 다음과 같이 과정을 설계할 수 있을 것이다:

• 두 물통의 물 차이가 리터가 될 때까지 물을 잘 옮긴다.
• 마지막 동작을 통해 차이를 실현한다.

따라서 대신 를 초기값으로 주어 위 과정을 반복하고, 마지막 동작에서 물통 1에서 물통 2로 물을 부어 물통 1에 리터를 남길 수 있다.

이때 물통 3에서 물통 1로 옮겨지는 물의 양을 계산하여 보자. 이때는 를 사용해야 한다. 인데, 옮겨지는 물의 양은 많아야 이고, 이므로 이 경우에도 물통 3에 만큼의 물이 있으면 항상 물을 옮길 수 있다.

위 동작 묶음을 수행하였을 때, 남아있는 물의 양 중 최솟값이 기존 최솟값의 보다 작거나 같게 된다. 최솟값을 줄이는 위의 과정을 동작 묶음이라고 부르자. 동작 묶음이 수행될 때마다 물의 양의 최솟값이 줄어들게 되므로, 동작 묶음을 유한하게 많이 사용하여 물통 하나를 비울 수 있다. 따라서 위 동작 묶음에 따라 동작을 나열하는 해답의 정당성이 증명된다.

분석: 동작 횟수

그러나 이 문제는 단지 동작을 나열할 뿐이 아니라, 동작의 횟수가 1000회로 제한되어 있다. 따라서 위 풀이를 검증하기 위해서는 동작의 정당성 뿐만 아니라 횟수에 대해서도 추가적인 분석이 필요하다.

풀이에 서술된 동작 묶음에 동작이 최대 몇 개 포함되었는지 분석하여 보자.

• 는 동작의 불변량이다.
• 일 때, 이므로, 이다.
• 이고, 이다. 그러므로 이다.
• 인 경우, 동작을 회 수행한다.
• 인 경우, 동작을 회 수행한다.

따라서 각 동작 묶음 당 최대 31회의 동작을 수행한다. 초기 최솟값은 이므로, 최솟값을 절반씩 줄이는 경우 동작 묶음을 최대 30회 사용한다. 따라서 위 풀이는 동작을 최대 회 수행한다. 이는 문제의 조건과 일치한다.

각 동작 묶음이 최대 31회까지 동작을 수행할 수도 있지만, 대부분의 경우 가 그렇게 크지는 않을 것으로 생각된다. 특히 현재의 최솟값이 인 경우, 이므로, 동작 묶음이 회 동작을 수행한다. 따라서 많아야 회의 동작을 수행할 것으로 보인다.

계산 복잡도

시간이 아주 오래 걸리지는 않는다. 각 동작 묶음마다 나눗셈를 수행하고, 를 이진 전개하면 된다. 시간 0ms으로 동작하는 해 또한 구성할 수 있다.

문제의 조건이 으로 주어졌을 때, 위 분석을 사용하면 답의 크기는 정도일 것으로 추측한다.