백준 14881 자바 - 물통 문제 (BOJ 14881 JAVA)

문제 : https://www.acmicpc.net/problem/14881

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14800/BOJ_14881.java

 

  처음엔 별 생각없이 brute force 정도로 생각했는데, 시간복잡도가 아닌 것 같아 다른 방법을 찾아봤다. 결론은 최대공약수 문제이다.

 

일단 되는 경우와 안되는 경우에 대해 생각해보자.

 

1. 일단 c가 a와 b 둘 모두보다 크다면 아예 불가능하다. (코드의 max>=c)

 

2. c가 a나 b와 동일하다면 당연히 가능하다. (코드의 a==c || b==c)

 

3. 다음으로 a,b의 최대공약수가 c의 공약수라면 가능하다. (코드의 c%gcd==0)

 

4. 마지막으로 a와 b가 서로소일 경우, 둘 중 큰 수 이하의 모든 수를 만들 수 있다. 이 부분이 찾기 어려웠다. (코드의 gcd==1)

 

예를들어 a==5, b==2를 보자. 둘은 서로소이다.

다음과 같이 모든 리터가 가능하다. (위에서부터 순서대로 보면 된다. 빨간 숫자는 해당 순서에서 발견한 리터)

 

최대공약수 구하는건 유클리드 호제법을 사용했다. (코드의 gcd())