[Algorithm] C++ 백준 23575번: Squid Game

문제 요약

문제 링크: https://www.acmicpc.net/problem/23575

세 개의 물통에 각각 $X, Y, Z$ 리터의 물이 있습니다. 한 물통에서 다른 물통으로 붓는 연산을 수행하되, 규칙에 따라 받는 물통의 양을 정확히 두 배로 만들어야 합니다. 최대 1000번 이내에 한 물통을 완전히 비워야 합니다.

입출력 형식:

1
2
3
4
5
입력: X Y Z
출력: 
  m (붓기 연산 수)
  A B (각 연산: 물통 A에서 물통 B로 붓기)
  ...

예제:

입력	출력
1 2 3	2 3 2 2 3 1 1
1 4 6	3 2 1 3 1 1 1 3 1

접근 개요

핵심 관찰

이 문제는 유클리드 호제법과 이진수 표현을 결합한 구성적 알고리즘입니다.

유클리드 호제법 유추: 세 물통을 크기순으로 $A \le B \le C$로 정렬하면, $B$를 $A$로 나눈 몫과 나머지를 이용하여 문제를 축소할 수 있습니다.
이진 분해: $B = qA + r$ (단, $q = \lfloor B/A \rfloor$)일 때, $q$를 이진수로 표현하면:
- 비트 1: $B$에서 $A$로 붓기 (B 감소)
- 비트 0: $C$에서 $A$로 붓기 (B 유지, A 증가)
반복: 이 과정을 반복하면 한 물통이 0이 되는 순간이 반드시 옵니다.

알고리즘 핵심 로직

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
while any bucket is non-zero:
  Sort buckets: A ≤ B ≤ C
  if A = 0: DONE
  
  q = B / A
  for each bit in q (from LSB):
    if bit = 1:
      pour(B → A)  // B -= A, A *= 2
    else:
      pour(C → A)  // C -= A, A *= 2

복잡도 분석

시간복잡도: $O(\log \min(X, Y, Z)^2)$
- 유클리드 호제법처럼 빠르게 수렴하므로 최대 1000번 이내
- 각 단계에서 정렬: $O(\log \text{iteration})$
공간복잡도: $O(m)$ (m은 붓기 연산 수)

구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct Bucket {
    long long amount;
    int index;
};

vector<pair<int, int>> result_moves;

void pour(Bucket& from, Bucket& to) {
    result_moves.push_back({from.index, to.index});
    from.amount -= to.amount;
    to.amount *= 2;
}

bool compareBuckets(const Bucket& a, const Bucket& b) {
    return a.amount < b.amount;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<Bucket> buckets(3);
    for (int i = 0; i < 3; ++i) {
        cin >> buckets[i].amount;
        buckets[i].index = i + 1;
    }

    while (true) {
        sort(buckets.begin(), buckets.end(), compareBuckets);

        if (buckets[0].amount == 0) break;

        // A = buckets[0], B = buckets[1], C = buckets[2]
        long long q = buckets[1].amount / buckets[0].amount;
        
        while (q > 0) {
            if (q % 2 == 1) {
                pour(buckets[1], buckets[0]);
            } else {
                pour(buckets[2], buckets[0]);
            }
            q /= 2;
        }
    }

    cout << result_moves.size() << "\n";
    for (const auto& move : result_moves) {
        cout << move.first << " " << move.second << "\n";
    }

    return 0;
}

정당성 증명

종료 조건

유클리드 호제법의 성질에 의해, 매 반복마다 최소 한 물통의 양이 감소합니다.
물통의 양은 항상 음이 아닌 정수이므로, 유한 번의 반복 후 반드시 한 물통이 0이 됩니다.
최악의 경우도 약 $\log \max(X, Y, Z)$ 정도의 반복으로 수렴하므로 1000번 이내입니다.

이진 분해의 정확성

$q$의 각 비트는 “몇 배를 부을 것인가"를 나타냅니다:

비트 1 ($k$번째): $A$를 $2^k$배로 만들면서, $B$에서 정확히 한 번 붓습니다.
비트 0: $C$의 충분한 물로 $A$만 키워서 비트 건너뛰기를 구현합니다.
$C \ge B$이므로 항상 충분한 물이 있습니다.

코너 케이스 체크리스트

케이스	설명	처리
X = Y = Z	모두 같은 경우	첫 붓기로 바로 한 물통이 0
X = 1	최소 단위	이진 분해가 최대 길이
Z = 10^9	최대값	64비트 정수로 안전 처리
큰 몫	q가 매우 큼	이진 표현이 길어도 복잡도 유지