-
백준 16943번 숫자 재배치PS 2020. 3. 17. 19:45
https://www.acmicpc.net/problem/16943
16943번: 숫자 재배치
두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.
www.acmicpc.net
<접근방법>
순열로 가능한 숫자배치를 만들어 본 후, 최대값을 구해줍니다.
string을 활용하면 구현이 쉽습니다.
0으로 시작하는 수는 후보에서 빼는 것도 고려해야 합니다.
<느낀 점>
<코드>
#include <iostream> #include <algorithm> #include <string> using namespace std; int a, b, res = -1; bool visit[10]; string tc, c; bool check() { if (stoi(c) <= b) return true; return false; } void dfs(int dep) { if(dep == tc.length()){ if (check()) { res = max(res, stoi(c)); } return; } for (int i = 0; i < tc.length(); i++) { if (visit[i]) continue; if (dep == 0 && tc[i] == '0') continue; c.push_back(tc[i]); visit[i] = true; dfs(dep + 1); c.pop_back(); visit[i] = false; } } int main() { cin >> a >> b; tc = to_string(a); dfs(0); cout << res << '\n'; return 0; }
반응형'PS' 카테고리의 다른 글
백준 16968번 차량 번호판1 (1) 2020.03.19 백준 17085번 십자가 2개 놓기 (1) 2020.03.18 백준 16945번 매직 스퀘어로 변경하기 (0) 2020.03.17 백준 16951번 블록 놀이 (0) 2020.03.17 백준 16937번 두 스티커 (0) 2020.03.15