알고리즘
[백준 알고리즘] 14881번 물통 문제. 파이썬(python)/ 최대공약수
삶은겨란
2022. 10. 19. 17:30
이해를 위한 글..
https://elwlsek.tistory.com/725
풀어보면 좋을 것 같은 문제인데 생각보다 푼 사람이 많이 없다.. 2551번 물통도 풀어보길 추천
https://www.acmicpc.net/problem/14881
14881번: 물통 문제
용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다.
www.acmicpc.net
주의)
c는 a, b보다 커야 한다.
a=2, b=2, c=4 일 때 NO가 되야 한다.
만약 다른 곳에 물을 저장할 수 있다면 2를 두 번 더해서 4로 만들 수 있지만
기존의 물통만 이용해야 하므로 크기가 2인 물통으론 4를 담을 수 없기 때문!
import sys
from math import gcd
input=sys.stdin.readline
t= int(input()) # 테스트 케이스
for _ in range(t):
a,b,c=map(int, input().split())
if c>a and c>b: # 크기 확인
print('NO')
else:
if c%gcd(a,b)==0: # a,b의 최대공약수
print('YES')
else:
print('NO')
만약 비커 3개(a, b, c)로 d리터를 만들어야 한다면? 똑같이 최소공배수를 이용해 풀면 된다.