반응형
https://www.acmicpc.net/problem/11311
11311번: Jug Hard
The first line contains T, the number of test cases (1 ≤ T 100 000). Each test case is composed of three integers: a b d where a and b (1 ≤ a, b ≤ 10 000 000) are the volumes of the two jugs, and d is the desired volume of water to be generated. You
www.acmicpc.net
[ 문제풀이 ]
1. a, b, d를 입력받고, d는 무조건 a 또는 b보다 작아야 d를 만들 수 있으므로 a >= d || b >= d인지 확인합니다.
2. a와 b를 이용해 만들 수 있는 수는 a와 b의 최대 공약수의 배수이면서 a와 b 중 더 큰 값보다 작거나 같은 수이므로 d가 a와 b의 최대공약수의 배수이면 Yes를 아니라면 No를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> using namespace std; int T; int a, b, d; int euclid(int a, int b) { while (b) { int tmp = a % b; a = b; b = tmp; } return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; while (T--) { cin >> a >> b >> d; if (a >= d || b >= d) { int tmp = euclid(a, b); if (d % tmp == 0) { cout << "Yes"; } else{ cout << "No"; } } else { cout << "No"; } cout << '\n'; } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14881번 - 물통 문제 (C++) (0) | 2023.10.25 |
|---|---|
| [ 백준 ] 20917번 - 사회적 거리 두기 (C++) (0) | 2023.10.24 |
| [ 백준 ] 1132번 - 합 (C++) (0) | 2023.10.23 |
| [ 백준 ] 4395번 - Steps (C++) (0) | 2023.10.22 |
| [ 백준 ] 17433번 - 신비로운 수 (C++) (0) | 2023.10.21 |