Boj 12886) 돌 그룹

문제

백준 12886

방법 1

설명

1. 세 수의 합은 항상 같으므로 dp[][] 는 두 수만 저장해도 된다.
2. 세 수는 순서가 관계 없으므로 정렬을 할 수 있고, 이러면 세가지 장점이 생긴다. 첫째로 움직일 수 있는 가능성이 6가지에서 3가지로 줄어들고, 둘째로 순서만 다르고 같은 수의 경우를 한번만 셈하게 되고, 셋째로 가장 큰 수가 최대 1300 을 넘어가는 경우도 있지만 작은 두 수만 기록하면 되므로 dp[][] 의 범위가 줄어든다.

시간 복잡도

O(\(N^2\))

코드

bool visits[501][1001];
struct D { int a, b, c; };

int main()
{
	fastio;

	D d; bool res = false;
	cin >> d.a >> d.b >> d.c;
	int sum = d.a + d.b + d.c;
	if (sum % 3)
	{
		cout << 0; return 0;
	}
	
	queue<D> q; q.push(d);
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		sort((int*)&cur, (int*)&cur + 3);
		if (visits[cur.a][cur.b]) continue;
		visits[cur.a][cur.b] = true;
	
		if (cur.a == cur.b && cur.b == cur.c) {
			res = true; break;
		}
		if (cur.a < cur.b)
			q.push({ cur.a << 1, cur.b - cur.a, cur.c });
		if (cur.a < cur.c)
			q.push({ cur.a << 1, cur.b, cur.c - cur.a });
		if (cur.b < cur.c)
			q.push({ cur.a, cur.b << 1, cur.c - cur.b });
	}
	
	cout << res;
}

방법 2

설명

\(A+B+C = \mathrm{GCD}(A, B, C) \times 2^x \times 3\) 로 나타낼 수 있으면 같은 그룹으로 만들 수 있고 그 역도 마찬가지이다.

필요조건

\(A + B + C = \mathrm{GCD}(A, B, C) \times t = S\) 라고 하자. \(S\) 는 이후 돌을 움직이는 과정에서 바뀌지 않는 상수임에 유의하자.

여기서 돌을 움직인 결과를 \((A+A, B-A, C)\) 라고 하면 돌을 움직인 결과의 최대공약수는 \(\mathrm{GCD}(A, B, C)\) 이거나 혹은 \(2\times GCD(A, B, C)\) 가 될 수 있다. 왜냐하면 돌을 움직일 때 \(A, B, C\) 각각을 더하고 빼기만 하므로 여전히 \(\mathrm{GCD}(A, B, C)\) 가 공약수이고, 한쪽이 \(A+A = 2A\) 이기 때문에 여기서 2가 추가될 가능성만 있기 때문이다. 이를 성질 1 이라고 하자.

그룹이 모두 같은 크기가 되면 최대공약수는 곧 그룹의 크기와 같다. 이때의 그룹의 크기를 \(M\) 이라고 하면 \(S = 3M\) 이 될 것이다. 그러면 성질 1에 의해서 임의의 자연수 \(x\) 에 대해서 \(M = S/3 = \mathrm{GCD}(A, B, C) \times 2^x\) 가 만족되어야 한다.

충분조건

임의의 상태에서 최대공약수에 2를 곱할 수 있는 경우가 있음을 보이면 이를 재귀적으로 반복할 수 있으므로 증명하는데 충분할 것이다.

\(A\) 와 \(B\) 의 그룹을 움직인다고 하자. \(B-A\) 는 최대공약수로 인수분해하면 \(\mathrm{GCD}(A, B, C)(B' - A')\) 로 나타낼 수 있다.

\(B'\) 와 \(A'\) 가 모두 짝수이면 \(A + B + C = \mathrm{GCD}(A, B, C) \times 2^x \times 3\) 이므로 \(C' = C/ \mathrm{GCD}(A,B,C)\) 도 짝수여야 한다. 그러면 최대공약수가 아니게 되므로 모순이다.

만약 둘 다 홀수이면 \(B'-A'\) 는 짝수이므로 \(C\) 가 짝수라면 최대공약수에 2가 추가된다. 그리고 \(C'\) 가 홀수이면 \(A + B + C\) 가 홀수가 되어 모순이므로 짝수여야만 한다.

만약 하나만 짝수이면 돌을 움직일 때 짝홀이 뒤바뀐다. 이렇게 해서 \(C\) 와 크기를 다르게 만드는 것을 보장하고, 둘중 홀수인 그룹과 \(C\) 를 움직이면 최대공약수에 2가 추가된다. 왜냐하면 위와 같은 이유로 \(C\) 가 홀수이기 때문이다.

이렇게 \(A\) 와 \(B\) 와의 이동에서 항상 최대공약수에 2를 곱할 경우가 있음을 보였고, \(A\) 와 \(C\) 와의 경우도 같은 작업을 할 수 있다. 그리고 한번 움직인 결과를 다시 정렬해서 위의 작업을 반복할 수 있다. 그러므로 이를 반복하면 언젠가 동일한 수가 되므로 증명 끝.

시간 복잡도

O(\(\log{500}\))

코드

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int sum = a + b + c;
    sum /= gcd(gcd(a, b), c); 
    if(sum % 3 == 0) 
    {
        sum /= 3;
        while (sum)
        {
            if (sum == 1) { cout << 1; break;}
            if (sum % 2)  { cout << 0; break; }
            sum >>= 1;
        }        
    }
    else cout << 0;
}