백준: 12886 돌 그룹

문제

12886번: 돌 그룹

 

문제 풀이

  돌의 개수가 다른 세 개의 그룹 A, B, C가 주어 질 때 세 개의 그룹 중 2개를 선택한 후, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 한다. 이때, X에 있는 돌의 개수를 X + X로 Y에 있는 돌의 개수를 Y - X개로 만든다. 이와 같은 방식으로 모든 경우의 수를 진행하여 A, B, C의 돌의 개수가 같아지는지 여부를 반환하는 문제이다.

 

• 그룹의 돌의 개수 합이 3으로 나누어지는 경우, 돌의 개수가 같아 질 수 없다.
• A, B, C 3개의 그룹 중 2개를 선택하여 2개의 크기를 비교하여 문제 조건과 같이 처리한다.
  • 딕셔너리를 활용하여, 동일한 조건을 재탐색하지 않도록 한다.

 

코드

from sys import stdin
from collections import deque, defaultdict


def bfs():
    q = deque([stones])
    check[tuple(stones)] = True

    while q:
        a, b, c = q.popleft()
        if a == b == c:
            return 1

        for x, y in ((a, b), (a, c), (b, c)):
            if x == y:
                continue
            elif x < y:
                y -= x
                x += x
            elif x > y:
                x -= y
                y += y

            z = sum_stone - x - y

            if not check[(x, y, z)]:
                check[(x, y, z)] = True
                q.append([x, y, z])

    return 0


if __name__ == '__main__':
    stones = list(map(int, stdin.readline().split()))
    sum_stone = sum(stones)
    check = defaultdict(bool)
    print(0) if sum_stone % 3 else print(bfs())

 defaultdict를 이용하여 x, y, z를 키로 사용하여 경우의 수에 대한 확인을 진행하였다. 메모리 초과나, 실행 초과가 발생하지 않았다.🙂