문제 요약 및 풀이
야간 당직을 서면서 직접 숫자를 만들어 나열해가다가, 아이디어가 떠올랐다.
임의의 어떤 수 A와 B가 있을 때, 두 수를 합친 AB와 BA가 있다면, 그 두 수중 큰 숫자를 선택하는 상황이다.
그럼 점차 합쳐지는 과정에서도 똑같은 규칙이 적용되는 것이니, 정렬을 해당 기준으로 하고 나중에 합치면 되지 않을까?
풀이시에 주의하기…
- ull 타입 사용하기, 오버플로우 주의
- 0000…000 은 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 <bits/stdc++.h>
using namespace std;
#define for1(s, e) for(int i = s; i < e; i++)
typedef unsigned long long ull;
ull ar[1100];
ull zero(ull a) {
ull ret = 1;
if(a == 0) return 10;
while(a > 0) {
ret *= 10;
a /= 10;
}
return ret;
}
bool compare(ull a, ull b) {
ull x = a * zero(b) + b;
ull x2 = b * zero(a) + a;
if(x <= x2) return false;
return true;
}
void solve() {
int N;
cin >> N;
for1(0, N) {
cin >> ar[i];
}
sort(ar, ar+N, compare);
if(ar[0] == 0) {
cout << 0;
return;
}
for1(0, N) {
cout << ar[i];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int tc = 1; // cin >> tc;
while(tc--) solve();
}