일단 아닌 경우를 전부 걸러 보았다.
1. a의 길이가 b의 길이보다 긴 경우 -> 이건 절대 네버 불가
2. b의 길이가 a의 길이보다 긴 경우 -> 무조건 된다 a를 가장 큰 수로 만들어주자
3. a와 b의 길이가 같은 경우 -> a의 순서를 섞으면서 조건에 맞는지 고민하면 된다......
3번의 경우가 되었을 때 어떻게 할지 고민하다가 처음에는 a의 counting 배열을 만든 다음 뒤에서부터 b랑 ㅣㅂ교하며 읽으면 안될까? 싶었는데
a : 3412 b: 3000인 경우 a가 처음 3을 선택할꺼고 b가 0임을 확인한 이상 돌이킬 수 없는 강을 건너게 되므로 패스했다.
다음으로 그냥 a의 순열을 다 만든 다음 b랑 비교해서 작은 걸 선택하면 되겠다 싶었다.
그래서 전에 만든 순ㄴ열코드 들고와서 이리저리 만들었는데 틀렸넹ㅎㅎ
지금 글 적으면서 생각난건데 뭔가 0 때문에 문제가 생긴게 아닐까 싶다.. 아님 뭐가 문제지
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
int v[10];
bool visited[10];
vector<int> selects;
int ans = 0;
int n, m;
void comb(int depth)
{
if (depth == n)
{
string str;
for (int i = 0; i < n; i++)
{
str += to_string(selects[i]);
}
int num = stoi(str);
if (ans < num && num <= m)
ans = num;
return;
}
for (int i = 0; i < n; i++)
{
if (visited[i])
continue;
visited[i] = true;
selects.push_back(v[i]);
comb(depth + 1);
visited[i] = false;
selects.pop_back();
}
}
int main()
{
string a, b;
cin >> a >> b;
if (a.size() > b.size())
{
printf("-1\n");
return 0;
}
if (a.size() < b.size())
{
sort(all(a), greater<char>());
cout << a;
return 0;
}
n = a.size();
m = stoi(b);
for (int i = 0; i < a.size(); i++)
{
v[i] = a[i] - '0';
}
comb(0);
if (ans == 0)
printf("-1\n");
else
printf("%d\n", ans);
return 0;
}
떼이잉~ 0으로 시작하면 안 된다는게 0012 말고 12로 적으라는 뜻인 줄 알았는데 0으로 시작하지 말라는 뜻이었다.
보통 0으로 시작할 수 없다고 적어놓으면 0으로 시작하지 말라는 거고 0을 적으면 안 되는 건 따로 명시를 해준다고 한다. 알아두겠서
해결은 간단했다. 0으로 시작하면 패스하게 했음
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
int v[10];
bool visited[10];
vector<int> selects;
int ans = 0;
int n, m;
void comb(int depth)
{
if (depth == n)
{
string str;
if (selects[0] == 0)
return;
for (int i = 0; i < n; i++)
str += to_string(selects[i]);
int num = stoi(str);
if (ans < num && num <= m)
ans = num;
return;
}
for (int i = 0; i < n; i++)
{
if (visited[i])
continue;
visited[i] = true;
selects.push_back(v[i]);
comb(depth + 1);
visited[i] = false;
selects.pop_back();
}
}
int main()
{
string a, b;
cin >> a >> b;
if (a.size() > b.size())
{
printf("-1\n");
return 0;
}
if (a.size() < b.size())
{
sort(all(a), greater<char>());
cout << a;
return 0;
}
n = a.size();
m = stoi(b);
for (int i = 0; i < a.size(); i++)
{
v[i] = a[i] - '0';
}
comb(0);
if (ans == 0)
printf("-1\n");
else
printf("%d\n", ans);
return 0;
}
'백준' 카테고리의 다른 글
10823 더하기 2 (0) | 2020.09.16 |
---|---|
2194 유닛 이동시키기 (0) | 2020.09.11 |
14465 소가 길을 건너간 이유 5 (0) | 2020.09.09 |
1966 프린터 큐 (0) | 2020.09.09 |
5568 카드 놓기 (0) | 2020.09.09 |