💛IV [백준 12886/C++] 돌그룹

BOJ 문제 보기

1. 문제

1. $A, B, C \leq 500$

2. 크기가 같지 않은 두 그룹을 골라 작은 쪽을 X, 큰 쪽을 Y로 지정

   • $X \rightarrow X + X$

   • $Y \rightarrow Y - X$

3. 세 돌 그룹을 같은 개수로 만들 수 있으면 1, 아니면 0 출력

한 정점에서 다른 정점으로 이동할 수 있는지 묻는 문제이므로, DFS와 BFS를 모두 사용할 수 있다.

---

2. 풀이 과정

정점의 단위를 (A, B, C)라고 가정하면 돌 그룹이 이동할 수 있는 경우의 수는 $1500^{3}$가 되므로 너무 많은 공간과 시간을을 필요로 한다.

돌이 움직이는 단계는 세 그룹을 한 번에 모두 이동시키는 것이 아니라, 두 그룹을 뽑아 계산하는 것이므로 메모리를 줄일 수 있다.

전체 돌의 개수 N과 두 개의 돌 그룹 A, B를 알고 있다면 C=N-(A+B)와 같이 유도할 수 있다.

정점의 단위를 두 개로 줄이면 필요한 공간의 수는 $1500^{2}$로 BFS를 활용해 충분히 문제를 해결할 수 있다.