(16496) 큰 수 만들기

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 6번째

 

 

 

S1, S2, ... , Si, Sj, ... ,Sn 순서로 나열된 어떤 숫자가 있다고 하자.

여기서 Si와 Sj의 순서를 바꿔도 길이의 합은 같으므로 다른 수에는 영향을 주지 않는다.

따라서 Si, Sj와 Sj, Sj로 이어붙인 결과 중 큰 값을 갖는 쪽으로 정렬하면 된다.

구두 수선공 문제와 다르게 정렬 식을 변형해 상대의 요소를 분리할 수 없지만 추이성과 비대칭성을 만족하므로 정렬에는 문제가 없다.

추이성: A<B, B<C이면 A<B는 항상 성립함

비대칭성: A<B이면 B<A는 항상 성립하지 않음

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  bool nonzero= false;;
  
  cin >> n;
  
  vector<string> v(n);
  
  for(int i=0;i<n;i++){
    cin >> v[i];
    if(v[i][0]!='0')  nonzero= true;
  }
  
  sort(v.begin(), v.end(), [](string A, string B){
    return A+B>B+A;
  });
  
  if(!nonzero){
    cout << 0;
  }else{
    for(string elem:v)  cout << elem;
  }
  
  return 0;
}