반응형

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

 

1039번: 교환

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N의 값이 10보다 작으면 -1을 츨력합니다.

 

2. n번 연산을 진행했을 때 숫자의 방문 여부를 체크할 visited [ num ][ n ] 배열을 만듭니다.

 

3. bfs를 활용하여 각각의 자릿수를 바꾸고 queue에 넣으면서 방문 처리를 해줍니다.

 

4. 교환 중 제일 앞자리 숫자가 0이 되면 안되므로 continue 해줍니다.

 

5. K번 연산을 진행했을 때 최댓값을 ans에 저장합니다.

 

6. 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
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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
int N, K;
int visited[1000001][11];
 
struct node {
    vector<int> num;
    int cnt;
};
 
int getDigit(int num)
{
    int ret = 1;
 
    while (1) {
        if (num < pow(10, ret)) {
            return ret;
        }
        ret++;
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    vector<int> num;
 
    if (N < 10) {
        printf("%d", -1);
        return 0;
    }
 
    int digit = getDigit(N);
 
    num.resize(digit);
 
    for (int i = digit-1; i >= 0; i--) {
        num[i] = N / pow(10, i);
        N %= (int)pow(10, i);
    }
 
    queue<node> q;
 
    q.push({ num,0 });
 
    int ans = -1;
 
    while (!q.empty()) {
        vector<int> cur = q.front().num;
        vector<int> a = q.front().num;
        int cnt = q.front().cnt;
        q.pop();
        int num = 0;
 
        if (cur[digit - 1] == 0) continue;
        if (cnt > K) continue;
 
        for (int i = 0; i < digit; i++) {
            num += cur[i] * pow(10, i);
        }
 
        if (visited[num][cnt] == 1) continue;
        visited[num][cnt] = 1;
 
        if (cnt == K) {
            ans = max(ans, num);
        }
 
        for (int i = 0; i < digit - 1; i++) {
            for (int j = i + 1; j < digit; j++) {
                if (i != j) {
                    cur = a;
                    int temp = cur[i];
                    cur[i] = cur[j];
                    cur[j] = temp;
 
                    q.push({ cur,cnt + 1 });
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 14466번 - 소가 길을 건너간 이유 6 (C++)  (0) 2022.12.02
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
[ 백준 ] 2550번 - 전구 (C++)  (0) 2022.11.28

+ Recent posts

티스토리툴바