[문제 바로가기] https://www.acmicpc.net/problem/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을 출력한다.
💡 문제 풀이
※유사한 문제 : 물통
visited를 비효율적으로 처리하여 '시간초과'로 고생한 문제...
BFS 알고리즘으로 가능한 A, B, C 그룹을 만들며 A = B = C가 가능한지 확인하면 된다.
일반적으로 visited를 일차원 배열로 두어 방문한 지점(좌표)을 담아서 방문 여부를 파악하였는데 이 문제의 경우 (500, 1, 1)과 같은 예제가 주어질 경우 꽤나 많은 좌표를 담기 때문에 'in'을 사용해서 방문 여부를 파악할 때 비효율적인 시간복잡도가 발생한다.
또한, (500, 1, 1)의 경우에는 (499, 2, 1)과 (499, 1, 2)로 나올 수 있는데 위 두 가지는 순서만 다르지 같은 경우이기 때문에 굳이 두 번의 확인을 진행할 필요는 없다.
즉, 두 개의 그룹만 정해지만 나머지 하나의 그룹은 자동으로 정해지기 때문에 2차원 배열로 visited를 만들면 방문 여부 파악이 훨씬 빠르고(인덱스를 사용하기 때문) 메모리도 적절하게 사용할 수 있다.
step 1)
3개의 그룹을 크기 순으로(A >= B >= C) 정렬한다.
크기 순으로 정렬할 경우 나올 수 있는 경우는 3가지다.
- A-B, B+B, C
- A-C, B, C+C
- A, B-C, C+C
step 2)
위 3가지 경우 중 '큰 물통 - 작은 물통 > 0'인 경우 check 함수를 실행한다.
step 3)
step 2)를 만족하는 3가지 수를 다시 정렬하고 방문여부 확인(visited) 후 visited와 queue를 최신화한다.
queue에 넣으면서 visited 및 queue를 최신화하며 A = B = C인 경우를 찾으면 된다. - BFS
step 4)
step 1) ~ step 3) 과정을 거치며 'a = b = c'인 경우가 나타나면 '1'을 출력하고 종료한다.
BFS 탐색을 마칠 때까지 찾지 못하면 0을 출력한다.
코드는 다음과 같다.
from collections import deque
numbers = list(map(int, input().split()))
A = max(numbers)
C = min(numbers)
B = sum(numbers) - A - C
queue = deque([(A, B, C)])
visited = [[False] * 1501 for _ in range(1501)]
visited[A][B] = True
def check(A, B, C):
a, c = max(A, B, C), min(A, B, C)
b = A+B+C-(a+c)
if not visited[a][b]:
visited[a][b] = True
queue.append((a, b, c))
return True
return False
while queue:
a, b, c = queue.popleft()
if a == b == c:
print(1)
break
temp_a1, temp_b1, temp_c1 = a-b, b+b, c
temp_a2, temp_b2, temp_c2 = a-c, b, c+c
temp_a3, temp_b3, temp_c3 = a, b-c, c+c
if temp_a1 > 0:
check(temp_a1, temp_b1, temp_c1)
if temp_a2 > 0:
check(temp_a2, temp_b2, temp_c2)
if temp_b3 > 0:
check(temp_a3, temp_b3, temp_c3)
else:
print(0)
