알고리즘

[백준 알고리즘] 14881번 물통 문제. 파이썬(python)/ 최대공약수

삶은겨란 2022. 10. 19. 17:30

이해를 위한 글..

https://namu.wiki/w/%EC%9B%90%ED%95%98%EB%8A%94%20%EB%AC%BC%EC%9D%98%20%EC%96%91%20%EC%96%BB%EA%B8%B0

 

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리터를 만들어야 한다면? 똑같이 최소공배수를 이용해 풀면 된다.