N이 100만보다 작다는 조건 덕분에 문제를 해결할 수 있었다.
최대 10번의 교환을 수행할 수 있기 때문에, 몇 번째 교환일 때 어떤 수가 나왔는지 확인한다면
모든 경우의 수를 확인해서 최솟값을 찾을 수 있다. -> check[1000001][11]
처음 숫자가 한자릿수라면 교환이 불가능하기 때문에 -1을 출력한다.
처음 숫자가 두자릿수일 때 일의 자리가 0이라면 교환이 불가능하기 때문에 -1을 출력한다.
dp를 수행하면서 교환한 수가 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
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
typedef long long ll;
// typedef pair<int, int> pii;
using namespace std;
string number;
int N, M, K;
int check[1000001][11];
void input(){
cin >> number >> K;
N = stoi(number);
ans = N;
M = number.size();
memset(check, -1, sizeof(check));
}
int dfs(string now, int kcnt){
if(kcnt == K) return stoi(now);
int &ret = check[stoi(now)][kcnt];
if(ret != -1) return ret;
for(int i = 0; i < M; i++){
for(int j = i+1; j < M; j++){
string temp = now;
swap(temp[i], temp[j]);
if(temp[0] == '0') continue;
ret = max(ret, dfs(temp, kcnt+1));
}
}
return ret;
}
int main(){
input();
if(M == 1 || (M == 2 && number[1] == '0')) cout << -1;
else cout << dfs(number, 0);
return 0;
}
|
cs |
'Algorithm > BOJ' 카테고리의 다른 글
[백준 3020] 개똥벌레 (C++) (0) | 2022.01.09 |
---|---|
[백준 1649] 택시 (C++) (0) | 2022.01.07 |
[백준 1368] 물대기 (C++) (0) | 2022.01.04 |
[백준 1322] X와 K (C++) (0) | 2021.12.08 |
[백준 20928] 걷는 건 귀찮아 (C++) (0) | 2021.12.04 |