돌 그룹(12886번) - 파이썬(Python)

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

12886번: 돌 그룹

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

예제

Example 1:

Input: 
10 15 35
Output: 
1

Example 2:

Input:
1 1 2
Output:
0

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

BFS로 해결하였다. 우선 비교할 때 비교대상이 같은 경우는 한쪽이 0이 되므로 같아질 수 없다고 생각했고 비교대상이 한쪽이 한쪽의 2배라면 X+X, Y-X 연산을 해도 결과가 같기 때문에 위 두 경우를 제외하며 진행하였다.

visited같은 경우에는 처음에는 리스트로 받아서 했는데 시간 초과가 나서 defaultdict(bool)을 활용하니 잘 되었다. 앞으로 defaultdict을 많이 활용해야겠다는 생각이 든다.

from collections import deque, defaultdict
import sys
a, b, c = map(int, input().split())

q = deque()
q.append([a, b, c])
visited = defaultdict(bool)

while q:
    na, nb, nc = q.popleft()
    if na == nb == nc:
        print(1)
        sys.exit()

    sub = sorted([na,nb,nc])
    # 0, 1
    if sub[0] == sub[1] or 2*sub[0] == sub[1]:
        pass
    else:
        n_sub = sorted([2*sub[0], sub[1]-sub[0],sub[2]])
        if not visited[tuple(n_sub)]:
            visited[tuple(n_sub)] = True
            q.append(n_sub)
    # 0, 2
    if sub[0] == sub[2] or 2*sub[0] == sub[2]:
        pass
    else:
        n_sub = sorted([2*sub[0], sub[2]-sub[0],sub[1]])

        if not visited[tuple(n_sub)]:
            visited[tuple(n_sub)] = True
            q.append(n_sub)
    # 1, 2
    if sub[1] == sub[2] or 2*sub[1] == sub[2]:
        pass
    else:
        n_sub = sorted([2*sub[1], sub[2]-sub[1],sub[0]])
        if not visited[tuple(n_sub)]:
            visited[tuple(n_sub)] = True
            q.append(n_sub)
print(0)