반응형

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
반응형

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

 

14881번: 물통 문제

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. a, b, c를 입력받고, c는 무조건 a 또는 b보다 작아야 c를 만들 수 있으므로 a >= c || b >= c인지 확인합니다.

 

2. a와 b를 이용해 만들 수 있는 수는 a와 b의 최대 공약수의 배수이면서 a와 b 중 더 큰 값보다 작거나 같은 수이므로 c가 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, c;
 
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 >> c;
 
        if (a >= c || b >= c) {
            int tmp = euclid(a, b);
 
            if (c % tmp == 0) {
                cout << "YES";
            }
            else{
                cout << "NO";
            }
        }
        else {
            cout << "NO";
        }
 
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11311번 - Jug Hard (C++)  (0) 2023.10.26
[ 백준 ] 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
반응형

https://www.acmicpc.net/problem/17433

 

17433번: 신비로운 수

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 첫째 줄에 N, 둘째 줄에 N개의 정수가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 정렬하고, 인접한 수들의 차를 dif 배열에 저장합니다.

 

2. dif 배열의 인접한 수들끼리 유클리드 호제법을 사용하여 최대 공약수를 ans에 저장합니다.

 

3. ans가 0이라면 INFINITY를 출력하고, 그렇지 않다면 ans를 출력합니다. 

 

[ 소스코드 ]

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
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int arr[2000];
int dif[2000];
int T, N;
int ans;
 
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 >> N;
 
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
 
        sort(arr, arr + N);
 
        for (int i = 0; i < N - 1; i++) {
            dif[i] = arr[i + 1] - arr[i];
        }
 
        ans = dif[0];
 
        for (int i = 1; i < N - 1; i++) {
            ans = euclid(ans, dif[i]);
        }
 
        if (ans == 0) {
            cout << "INFINITY\n";
        }
        else {
            cout << ans << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
반응형

https://www.acmicpc.net/problem/1684

 

1684번: 같은 나머지

첫째 줄에 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 절댓값이 1,000,000을 넘지 않는 n개의 정수들이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 정렬하고, 인접한 수들의 차를 dif 배열에 저장합니다.

 

2. dif 배열의 인접한 수들끼리 유클리드 호제법을 사용하여 최대 공약수를 ans에 저장합니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
47
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n;
int arr[1000];
int dif[1000];
int ans;
 
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 >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n - 1; i++) {
        dif[i] = arr[i + 1] - arr[i];
    }
 
    ans = dif[0];
 
    for (int i = 1; i < n - 1; i++) {
        ans = euclid(ans, dif[i]);
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
반응형

https://www.acmicpc.net/problem/2436

 

2436번: 공약수

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 최소공배수를 최대공약수로 나눈 값을 ab로 두고, ab = a x b로 나타냅니다. 

 

2. a와 b의 최대공약수가 1인 쌍을 ans에 저장합니다.

 

3. 최소공약수 * (a + b)의 값이 최소인 쌍을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int A, B;
vector<pair<int, int>> ans;
int idx;
 
int Euclid(int B, int A) {
    while (B != 0) {
        int temp = A % B;
        A = B;
        B = temp;
    }
 
    return A;
}
 
int main()
{
    scanf("%d %d", &A, &B);
 
    int temp = B / A;
 
    for (int i = 1; i*i <= temp; i++) {
        if (temp % i == 0) {
            if (Euclid(i, temp / i) == 1) {
                ans.push_back({ i * A, temp / i * A });
            }
        }
    }
 
    int min = 987654321;
 
    for (int i = 0; i < ans.size();i++) {
        if (min > ans[i].first + ans[i].second) {
            min = ans[i].first + ans[i].second;
            idx = i;
        }
    }
 
    printf("%d %d", ans[idx].first, ans[idx].second);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1253번 - 좋다 (C++)  (0) 2023.04.15
[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
[ 백준 ] 1484번 - 다이어트 (C++)  (0) 2023.04.12
[ 백준 ] 20366번 - 같이 눈사람 만들래? (C++)  (0) 2023.04.11
[ 백준 ] 13144번 - List of Unique Numbers (C++)  (0) 2023.04.10

+ Recent posts

티스토리툴바