[C++] 백준 21740 도도의 수학놀이

내가 만든 문제지만 중간중간 함정도 있고

신경써야 할 부분도 많아 어려웠다.

 

 

일단 모든 수를 180도 회전시키고 생각을 해봐야 한다.

 

 

1. a+b 와 b+a 의 대소비교를 통하여 a와 b중 뭐가 앞에 와야하는 지 알 수 있다.

 

bool cmp(string a, string b) {return a+b > b+a;}

 

우리가 봐야 하는 것은 두 숫자를 이어붙였을 때의 숫자이다.

따라서 문자열로 두고 a를 앞에 붙인 것과 b를 앞에 둔 것을 비교해서

정렬할 수 있다.

 

문자열로 비교해서 차이가 날 수 있지 않냐는 우려가 있을수 있지만

a+b와 b+a의 문자열의 길이는 같다.

 

따라서 a+b와 b+a의 대소비교는 int(a+b)와 int(b+a)의 대소비교와 똑같게 나온다.

 

2. 한 번 더 사용해야하는 수는 가장 큰 정수이다.

 

만약 98, 986을 1번의 우리 기준으로 정렬하면

98, 986이 된다.

 

만약 98이 가장 앞에있는 수라고 가장 클 것이라 생각해

98을 한 번 더 사용하게 된다면 98 98 986이 된다.

하지만 정답은 98 986 986이다.

 

이처럼 앞에 붙였을 때 가장 큰 수와

그냥 가장 큰 정수를 잘 파악해야 한다.

 

3. 수를 한 번 더 사용했으면 그만 사용해야 한다.

예를 들어 99, 99, 10이 있으면

99를 한 번 더 사용했는지 체크하지 않고 또 사용하게 된다면

99 99 99 99 10이라는 답이 나오게 된다.

 

 

정답 코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9+7;


ll gcd(ll a, ll b) {
    if (b) return gcd(b, a%b);
    return a;
}

ll ceil(ll a, ll b) {
    return (a-1)/b + 1;
}



void debug() {

}

//----------------------------------------------------------------------//

int toint(string a) {
    int ret = 0;
    for (auto i: a) ret = ret * 10 + int(i);
    return ret;
}

bool cmp(string a, string b) {return a+b > b+a;}

string reve(string a) {
    string ret = "";
    for (auto i: a) {
        if (i == '6') ret = '9' + ret;
        else if (i == '9') ret = '6' + ret;
        else ret = i + ret;
    }
    return ret;
}

int N;
string M = "0";
string arr[101010];

void solve() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        string a; cin >> a;
        arr[i] = reve(a);
        if (toint(M) < toint(arr[i])) M = arr[i];
    }
    arr[N] = M;
    sort(arr, arr+N+1, cmp);
    string ans = "";
    for (int i = N; i >= 0; i--) {
        cout << reve(arr[i]);
    }
}



int main() {
    FASTIO
    ll T=1;
    while (T--) solve();
}