[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


'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 12013번: 248  (0) 2018.05.24
[BOJ] 1214번: 쿨한 물건 구매  (0) 2018.05.24
[BOJ] 13258번: 복권 + 은행  (0) 2018.05.24
[BOJ] 14867번: 물통  (0) 2018.05.23
[BOJ] 14595번: 동방 프로젝트  (0) 2018.05.23
[BOJ] 3190번: zmjia  (0) 2018.05.17
[BOJ] 14956번: Philosopher's Walk  (3) 2018.05.17
  Comments
댓글 쓰기