반응형

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/28421

 

28421번: 곱하기와 쿼리

길이가 $N$인 수열 $A_1, A_2, A_3, \cdots, A_N$이 주어진다. 다음 질의를 수행하는 프로그램을 작성하시오. 1 $x$: 수열에서 서로 다른 두 수 $i$, $j$를 골라 $A_i$, $A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 저장할 arr[ N ] 배열을 선언합니다.

 

2. 각 수의 개수를 저장할 box[ 10001 ] 배열을 선언합니다.

 

3. 수열을 입력받고, 각 숫자들의 개수를 box 배열에 더해줍니다.

 

4. 쿼리를 입력받을 때마다 1부터 i * i <= x까지 for문을 돌면서 숫자의 존재를 box 배열을 통해 체크하고, 두 수를 곱해서 x를 만들 수 있다면 1을 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
 
using namespace std;
 
int N, Q;
int arr[100001];
int box[20001];
 
bool check(int x)
{
    int i = 1;
 
    if (N == 1) return false;
 
    if (x == 0) {
        if (box[0]) {
            return true;
        }
        else return false;
    }
 
    if (x > 10000) {
        i = x / 10000;
    }
 
    for (i; i * i <= x; i++) {
        if (box[i] && x % i == 0 && box[x / i]) {
            if (i * i == x && box[i] < 2) {
                continue;
            }
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        box[arr[i]]++;
    }
 
    for (int i = 0; i < Q; i++) {
        int cmd, x;
        cin >> cmd >> x;
 
        if (cmd == 1) {
 
            if (check(x)) {
                cout << 1;
            }
            else {
                cout << 0;
            }
 
            cout << '\n';
        }
        else {
            box[0]++;
            box[arr[x]]--;
            arr[x] = 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
반응형

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

 

1990번: 소수인팰린드롬

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 값이 10,000,000보다 큰 팰린드롬수는 없으므로 b = min(b, 10,000,000)을 통해 b를 갱신합니다.

 

2. a부터 b까지 for문을 통해 돌면서 팰린드롬 수인지 체크하고, 팰린드롬 수라면 소수인지 판정 후 출력합니다.

 

[ 소스코드 ]

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<string>
#include<algorithm>
 
using namespace std;
 
int a, b;
int prime[10000001];
 
bool check(int num)
{
    string temp = to_string(num);
    string temp2 = temp;
    reverse(temp.begin(), temp.end());
 
    if (temp != temp2) return false;
    return true;
}
 
bool isPrime(int num)
{
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> a >> b;
 
    b = min(b, 10000000);
 
    for (int i = a; i <= b; i++) {
        if (check(i)) {
            if (isPrime(i)) {
                cout << i << '\n';
            }
        }
    }
 
    cout << -1 << '\n';
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
반응형

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

 

1456번: 거의 소수

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

www.acmicpc.net

 

 

1. arr 배열을 만들어 각 소수 여부를 저장합니다.

 

2. 소수를 vector<ll> prime에 저장합니다.

 

3. for문을 통해 prime을 돌면서 거듭제곱을 해주고, 그 수가 A <= N <= B 라면 ans++를 해줍니다.  이때, 오버플로우가 날 수도 있어서 해당 값을 i로 나눈 나머지가 0일 때 조건을 추가해 줍니다.  

 

4. 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
#include<iostream>
#include<vector>
#define ll long long
 
using namespace std;
 
ll A, B;
int arr[10000001];
vector<ll> prime;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> A >> B;
 
    for (ll i = 2; i * i <=B; i++) {
        if (!arr[i]) {
            prime.push_back(i);
            for (int j = 2; i * j * i * j <= B; j++) {
                arr[i * j] = 1;
            }
        }
    }
 
    int ans = 0;
 
    for (ll i : prime) {
        if (!arr[i]) {
            ll temp = 1LL * i;
            while(1){
                temp *= 1LL * i;
                if (temp > B || temp % i != 0) break;
                if (temp < A) continue;
                ans++;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
반응형

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

 

11402번: 이항 계수 4

첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

 

https://rudalsd.tistory.com/426

 

1.  $_{n}\textrm{C}_{r} =\,    _{n-1}\textrm{C}_{r-1} +\,  _{n-1}\textrm{C}_{r}$ 이므로 분할정복을 이용하여 $_{n}\textrm{C}_{r}$를 구해줍니다.

 

2. 뤼카의 정리를 이용하여 각각의 조합의 값들을 곱해 M으로 나눈 나머지를 출력합니다.

 

[ 소스 코드 ]

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
57
58
#include<iostream>
#include<vector>
#define ll long long
 
using namespace std;
 
ll N, K;
int M;
ll arr[2001][2001];
 
vector<int> luca(ll N, int M)
{
    vector<int> ret;
 
    while (N) {
        int temp = N % M;
        ret.push_back(temp);
        N /= M;
    }
 
    return ret;
}
 
ll comb(int N, int R)
{
    if (N < R) return 0;
    if (R == 1) return N;
    if (R == 0) return 1;
    if (arr[N][R] != 0) return arr[N][R];
 
    return arr[N][R] = (comb(N - 1, R - 1) + comb(N - 1, R)) % M;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K >> M;
 
    vector<int> n, k;
 
    n = luca(N, M);
    k = luca(K, M);
 
    int idx = min(n.size(), k.size());
 
    ll ans = 1;
 
    for (int i = 0; i < idx; i++) {
        ans *= comb(n[i], k[i]);
        ans %= M;
        if (ans == 0) break;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
반응형

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

 

11401번: 이항 계수 3

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

 

https://rudalsd.tistory.com/61?category=1064608 

 

[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다. $a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족하고, 만약 $p$가 소수이고, $a$와 $p$가 서로소이면 $a^{p-1}\equiv 1($mod $p)$를 만족

rudalsd.tistory.com

 

1. 먼저 $\binom{N}{K}$는 다음과 같이 나타낼 수 있습니다.

 

$\binom{N}{K} = \frac{N!}{(N-K)!K!}$

 

2. 페르마의 소정리를 이용하여 mod $m$에서 어떤 수를 $a$로 나눈다는 뜻은 $a$의 역원을 곱한다는 뜻과 같습니다. 따라서 $m$이 소수일 때, $a^{m-1}\equiv 1($mod $m)$이고, $a\times a^{m-2}\equiv 1($mod $m)$이므로 mod $m$에서 $a$에 대한 곱셈의 역원은 $a^{m-2}$입니다.

 

따라서, 

 

$\frac{N!}{(N-K)!K!} \equiv N!\times ((N-K)!K!)^{m-2}($mod $m)$

 

이 됩니다.

 

3. 분모의 수로 나누는 방법 대신 $m-2$제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이때 $m$의 값이 $1,000,000,007$로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#define ll long long
#define M 1000000007
 
using namespace std;
 
ll Fac[4000001];
 
ll p(int n, int k)
{
    if (k == 0) return 1;
    if (k == 1) return n;
 
    if (k % 2 == 0) {
        ll temp = p(n, k / 2);
        temp %= M;
 
        return (temp * temp) % M;
    }
    else {
        ll temp = p(n, k - 1);
        temp %= M;
 
        return (temp * n) % M;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, K;
    cin >> N >> K;
 
    Fac[0] = 1;
    Fac[1] = 1;
 
    for (int i = 2; i <= N; i++) {
        Fac[i] = Fac[i - 1] * i;
        Fac[i] %= M;
    }
 
    ll ans = Fac[N] * p((Fac[N - K] * Fac[K])%M, M - 2);
    ans %= M;
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30
[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
반응형

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

 

1963번: 소수 경로

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 각 네 자릿수의 방문 여부를 저장합니다.

 

2. 에라토스테네스의 체를 이용하여 네 자릿수 소수들을 check 배열에 모두 저장합니다.

 

3. bfs를 이용하여 각 자릿수를 1씩 바꾸어주면서 방문 여부를 판별하고, 방문하지 않았다면 소수 여부를 판별하여 소수라면 queue에 넣어줍니다.

 

4. A 수가 B수로 변환이 가능하다면 cnt를 출력하고, 그렇지 않다면 Impossible을 출력합니다.

 

[ 소스코드 ]

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<queue>
 
using namespace std;
 
int T, A, B;
int check[10000];
int visited[10000];
 
int bfs(int A, int B)
{
    fill(visited, visited + 10000, 0);
    queue<pair<int, int>> q;
 
    q.push({ A,0 });
    visited[A] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (cur == B) {
            return cnt;
        }
 
        int temp = cur % 1000;
 
        for (int i = 1; i <= 9; i++) {
            int next = temp + i * 1000;
            if (visited[next] != 1) {
                visited[next] = 1;
                if (check[next] == 0) {
                    q.push({ next, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 100;
            if ((temp % 1000) / 100 == 0) temp -= 1000;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 10;
            if ((temp % 100) / 10 == 0) temp -= 100;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 1;
            if (temp % 10 == 0) temp -= 10;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 2; i <= 5000; i++) {
        for (int j = 2; j <= 5000; j++) {
            if (i * j < 10000) {
                check[i * j] = 1;
            }
            else break;
        }
    }
    
    while (T--) {
        cin >> A >> B;
 
        int temp = bfs(A, B);
 
        if (temp != -1) {
            cout << temp << '\n';
        }
        else {
            cout << "Impossible\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22

+ Recent posts

티스토리툴바