글 읽기 - 어떻게 접근해야 할 지 모르겠습니다.

tkdgus115 4년 전 0

일단 10⁵에서 2개를 고르는 방법이 10000000000 이니간 초과가 될깨 뻔한데

어떻게 2개의 수를 선택해야 되는지 감이 안잡힙니다.

힌트를 얻을수 있을까요??

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
vector<pair<int,string>> v;
int ans=-1;
void comp(string a, string b){
    int original_len=(int)a.size()+(int)b.size();
   
   
    vector<tuple<char,int,int>> v;
    for(int i=0;i<(int)a.size();i++){
        for(int j=(int)b.size()-1;j>=0;j--){
            if(b[j]==a[i]){
                v.push_back(make_tuple(a[i],i,j));
            }
        }
    }
    
    //a가 앞에 b가 뒤에
    for(int i=0;i<v.size();i++){
        char ch;
        int a_ind;
        int b_ind;
        tie(ch,a_ind,b_ind)=v[i];
        
        string a_temp=a.substr(0,a_ind);
        string b_temp=b.substr(b_ind);
   
        int len=(int)a_temp.size()+(int)b_temp.size();
        int t=original_len-len-1;
        if(ans==-1 || ans>t){
            ans=t;
        }
    }
    
    //b가 앞에 a가 뒤에
    for(int i=0;i<v.size();i++){
        char ch;
        int a_ind;
        int b_ind;
        tie(ch,a_ind,b_ind)=v[i];
       
        string b_temp=b.substr(0,b_ind);
        string a_temp=a.substr(a_ind);
        int len=(int)a_temp.size()+(int)b_temp.size();
        int t=original_len-len-1;
        if(ans==-1 || ans>t){
            ans=t;
        }
    }
}
int n;
int main(){
    cin>>n;string a;
    for(int i=0;i<n;i++){
        cin>>a;
        v.push_back(make_pair((int)a.size(), a));
    }
    sort(v.begin(),v.end());
    

    for(int i=0;i<n-1;i++){
        comp(v[i].second,v[i+1].second);
    }
    
    for(int i=0;i<n/2;i++){
        comp(v[i].second,v[n-i-1].second);
    }
 

    cout<<ans<<"\n";

    
}

cozyyg 4년 전 0

알파벳 소문자는 총 26개입니다. 이 알파벳들 각각에 대해 뭔가 작업을 해 주면 될 것 같습니다.

tkdgus115 4년 전 0

감사합니다 깊게 고민해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떻게 접근해야 할 지 모르겠습니다.

tkdgus115 4년 전 0

cozyyg 4년 전 0

tkdgus115 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말