오늘의 한 마디
없음

• Baekjoon 문제 링크
• 현재 백준 문제집: 단기간 성장을 풀고 있습니다.

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

예제 입력 1

10 15 35

예제 출력 1

1

예제 입력 2

1 1 2

예제 출력 2

0

발상

1. visited 배열 메모리에 대해

처음에는 visited[A][B][C]로 3차원 visited 배열을 만들어야 하나 싶었다.

하지만 돌의 총 개수는 변하지 않는다.

그래서 visited[최솟값][최댓값]만 저장해도 된다.
최솟값과 최댓값이 정해져 있는 상황에서는, 중간값은 이미 하나(TOTAL - 최솟값 - 최댓값)로 고정되어 있기 때문에 2차원 visited 배열로도 구현할 수 있다.

2. 어떤 돌에서 어떤 돌로 옮겨야 하는가?

돌이 세 그룹이라서 어디에서 어디로 어떤 기준으로 옮겨야 하는지 헷갈릴 수 있는데, 결론을 말하자면 각각의 케이스를 모두 테스트해봐야 한다.

A, B, C가 있으면, (A,B), (B,C), (C,A) 각각의 케이스에 대해 둘 사이에서 큰 쪽에서 작은 쪽으로 돌을 다 옮겨보아야 한다.

    for X, Y in [(a,b), (a,c), (b,c)]:
        if X == Y:
            continue
        if X > Y:
            X, Y = Y, X # 반드시 X에 작은 값이 오게 함. 

        X, Y = X+X, Y-X        
        min_ = min(X, Y, TOTAL - (X+Y))
        max_ = max(X, Y, TOTAL - (X+Y))
        if visited[min_][max_]:
            continue
        q.append((min_, max_))
        visited[min_][max_] = True

이런 느낌으로.

사용하는 알고리즘은 아주 기본적인 BFS라 어렵지 않다.

풀이

import sys
from collections import deque

A, B, C = map(int, sys.stdin.readline().rstrip().split())

# X+Y 를 X+X + Y-X 로 만들어도 개수에 변함은 없음. 
TOTAL = A+B+C
if TOTAL%3 != 0:
    print(0)
    exit()

visited = [[False]*TOTAL for _ in range(TOTAL)] # [최솟값][최댓값]으로 기록한다. 중간값은 빼면 알 수 있으니까.

q = deque([(A,B)])
visited[A][B] = True
while q:
    a, b = q.popleft()
    c = TOTAL - (a+b)
    if a == b == c:
        print(1)
        exit()
    for X, Y in [(a,b), (a,c), (b,c)]:
        if X == Y:
            continue
        if X > Y:
            X, Y = Y, X

        X, Y = X+X, Y-X        
        min_ = min(X, Y, TOTAL - (X+Y))
        max_ = max(X, Y, TOTAL - (X+Y))
        if visited[min_][max_]:
            continue
        q.append((min_, max_))
        visited[min_][max_] = True
print(0)