[BOJ] 14867번: 물통

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

일단 불가능한 경우와 자명한 경우부터 걸러냅니다. g = gcd(a,b)라고 할 때 c%g != 0이거나 d%g != 0이면 불가능합니다. 또 두 물통 모두 물이 어중간하게 남아있으면(꽉 찬것도 아니고 아예 빈 것도 아니면) 불가능합니다.

이제 생각을 해보면 결국 방식은 어느 한 물통에서 물을 계속 채우고, 다른 한 물통에서 계속 버리는 방법밖에 없으므로 A 물통에서 계속 물을 채웠을 때의 최소 횟수, B 물통에서 계속 물을 채웠을 떄의 최소 횟수를 계산하면 됩니다. 시간복잡도는 O(A+B)입니다.

BFS를 이용해도 풀 수 있습니다. 또 정답자 코드 중에 O(1)으로 푸는 코드도 있는데 봐도 잘 이해가 안갑니다.

https://github.com/blisstoner/BOJ/blob/master/14867.cpp