[BOJ] 12886 - 돌 그룹 (Python)

 

 

아이디어 #1

 

BFS로 세 그룹의 돌이 개수가 같아질 수 있는지 확인한다.

 

 

풀이 #1

 

import sys

input = sys.stdin.readline

def solution():
    A, B, C = map(int, input().split())
    if (A+B+C)%3:
        print(0)
    else:
        visited = dict()
        queue = [tuple(sorted([A, B, C]))]
        visited[queue[0]] = 1
        while queue:
            a, b, c = queue.pop(0)
            if a == b == c:
                print(1)
                break
            if a != b:
                temp = tuple(sorted([a+a, b-a, c]))
                if visited.get(temp, 0) == 0:
                    visited[temp] = 1
                    queue.append(temp)
            if a != c:
                temp = tuple(sorted([a+a, b, c-a]))
                if visited.get(temp, 0) == 0:
                    visited[temp] = 1
                    queue.append(temp)
            if b != c:
                temp = tuple(sorted([a, b+b, c-b]))
                if visited.get(temp, 0) == 0:
                    visited[temp] = 1
                    queue.append(temp)
        else:
            print(0)

solution()

 

 

 

아이디어 #2

 

세 그룹의 돌 개수의 최대공약수를 이용해 세 그룹의 돌을 같은 개수로 만들 수 있는지 확인한다.

 

 

풀이 #2

 

세 그룹의 돌을 같은 개수로 만들기 위해서는 모든 그룹의 돌 개수가 A, B, C의 평균이 되어야 한다.

각 단계에서 이동할 수 있는 돌 개수의 최솟값은 두 돌 개수의 최대공약수이고, 이동 후 개수가 적은 쪽은 2배가 된다.

따라서 A, B, C의 평균은 A, B, C의 최대공약수와 2의 거듭제곱의 곱이어야 한다.

 

A, B, C 합을 A, B, C의 최대공약수로 나눈 값이 3의 배수이고,

3으로 나눈 값이 2의 거듭제곱이라면 세 그룹의 돌을 같은 개수로 만들 수 있다.

 

def solution():

    def gcd(a, b):
        if a > b:
            a, b = b, a
        while a != 0:
            r = b%a
            b, a = a, r
        return b

    A, B, C = map(int, input().split())
    temp = (A+B+C)//gcd(A, gcd(B, C))
    print((temp%3 == 0 and bin(temp//3).count('1') == 1)*1)

solution()