[BOJ] 16496 큰 수 만들기

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

16496번: 큰 수 만들기

\(N\)개의 수를 그리디적으로 적절히 정렬할려고 한다.

어떤 두 수 \(A\), \(B\) 에 대해 \(AB\)랑 \(BA\) 중에 더 크게 되도록 정렬을 해주면 된다.

만약, \(AB\) > \(BA\) 라면 \(A\), \(B\) 순으로 정렬해주면 되고, 

반대라면 \(B\), \(A\) 순으로 정렬해주면 된다.

 

자리수를 구할때 입력받은 수가 0인 경우에 0자리라고 구해지는 경우와, 모든 수가 0인 경우를 조심해야 한다.

총 시간복잡도는 \(O(NlogN)\)이다.

 

재채점으로 인해 틀렸습니다.

나중에 시간이 되면 다시 풀고 작성해보겠습니다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n;
ll a[1005];

bool cmp(ll x,ll y) {
    ll l1 = 10, l2 = 10;
    ll tx = x/10, ty = y/10;
    while(tx) {
        l1 *= 10;
        tx /= 10;
    }
    while(ty) {
        l2 *= 10;
        ty /= 10;
    }
    return x*l2+y > y*l1+x;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    sort(a+1,a+n+1,cmp);
    if(!a[1]) cout << 0;
    else for(int i = 1;i <= n;i++) cout << a[i];
}