[C언어] 백준 14881 : 물통 문제

백준 14881 : 물통 문제

 

문제 링크

www.acmicpc.net/problem/14881

14881번: 물통 문제

 

 

문제 내용

용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다.

 

 

Idea

수많은 시행착오 끝에...

물통 문제에는 크게 두 가지 규칙이 있다.

(사실 저 1번에서 많이 틀려먹었다... 문제 좀 제대로 읽지...)

1. 물통은 a와 b만 있다. 즉, a나 b에 물을 채워 c를 만드는 것이 문제이다.(=a와 b보다 c가 크다면 만들 수 없다)
2. a와 b사이에 최대공약수가 없다면 a나 b이하의 모든 리터의 물을 만들 수 있다.

위 규칙을 토대로 코딩을 하면 끝이다. 단, c리터를 최대공약수로 나누어 떨어질 때도 "YES" 

 

 

Code

#include <stdio.h>
 
int main() {
    int T, a, b, c;
    scanf("%d", &T);
 
    for (int i = 0; i < T; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if (c > a && c > b) printf("NO\n");
        else {
            //a물통이 무조건 b보다 크도록 만든다.
            if (a < b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            int r;
            //최대공약수구하기
            while (b != 0) {
                r = a % b;
                a = b;
                b = r;
            }
 
            //결과출력
            if (a == 1 || c % a == 0) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

[ line 11 ~ line 23 ]

최대공약수 구하기.

위 식을 쓰기 위해서는 a가 무조건 커야 하며 while문을 종료하고 나올 때,

a가 1이라면 최대공약수가 없는 것이고

a가 2이상이라면 최대공약수가 존재하는 것이다.