백준 문제 16496번 큰 수 만들기 문제풀이 c++

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

16496번: 큰 수 만들기

 

문제해설

 

 

3으로 시작하는것중 일부분만 나타낸것인데 크게 만들기위해선

빨간 부분에 해당하면 오른쪽 아래것을 선택하는것이 좋고 파란 부분에 해당하면 오른쪽 위에있는 것을 선택하는것이 최적이다.

 

그렇다면 무수히 많은 빨간 부분과 파란부분이 나올것인데 처음에는 숫자로 생각해서 우선순위에 맞게 출력을 해도 대략 90퍼센트에서 계속 틀렸었다.

 

이걸 숫자가 아닌 문자열로 보면 이걸 아주 간단하게 표현할수있다.

왜 처음엔 왜 문자열로 생각할 생각을 못했는지..

위에서 설명한거 자체가 return (s1+s2>s2+s1); 이기 때문에 cmp함수를 작성해서 정렬하면 끝인거였다..

 

코드

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long int ll;
using namespace std;
bool cmp(string s1,string s2);
vector <string> v;
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n;
    string input;
    cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>input;
        v.push_back(input);
    }
    sort(v.begin(),v.end(),cmp);
    if(v[0]=="0")
    {
        cout<<0;
        return 0;
    }
    for(ll i=0; i<v.size(); i++)
    {
        cout<<v[i];
    }
    return 0;
}
bool cmp(string s1,string s2){
    return (s1+s2>s2+s1);
}