백준 1594 전화번호 만들기

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

1594번: 전화번호 만들기

재귀와 백트래킹을 이용해 구현했습니다.

 

같은 품질이 나올경우 사전순으로 앞선 문자열을 출력하는 것이 중요한데 '-'문자는 숫자들보다 앞서므로 재귀를 통해 번호를 2개씩 끊고 번호를 3개씩 끊게되면 사전순으로 탐색하게 됩니다.

 

또한 번호 경우의 수를 탐색할때 해당위치까지 과거에 탐색했던 최대 품질보다 적을경우 뒤를 탐색할 필요가 없게됩니다. 이를 통해 시간복잡도를 줄일 수 있습니다.

#include<stdio.h>
#include<iostream>
#include<string>
#include<set>
using namespace std;
int N;
string input;
int sn;
int bt[2001];
string solve;
void recur(string a,int now,int ret){
    string temp;
    if(bt[now]>=ret) return;
    bt[now]=ret;
    if(now==N){
        if(sn<ret){
            sn=ret;
            solve=a;
        }
        return;
    }
    set<int> s;
    for(int x=now;x<now+2;x++){
        if(x==N) return;
        temp.push_back(input[x]);
        s.insert(input[x]);
    }
    if(s.size()==1){
        if(now==0) recur(temp,now+2,ret+2);
        else recur(a+"-"+temp,now+2,ret+2);
    }
    else{
        if(now==0) recur(temp,now+2,ret);
        else recur(a+"-"+temp,now+2,ret);
    }
    if(now+2>=N) return;
    s.insert(input[now+2]);
    temp.push_back(input[now+2]);
    if(s.size()==1){
        if(now==0) recur(temp,now+3,ret+2);
        else recur(a+"-"+temp,now+3,ret+2);
    }
    if(s.size()==2){
        if(now==0) recur(temp,now+3,ret+1);
        else recur(a+"-"+temp,now+3,ret+1);
    }
    if(s.size()==3){
        if(now==0) recur(temp,now+3,ret);
        else recur(a+"-"+temp,now+3,ret);
    }
}
int main(){
    cin>>input;
    N=input.size();
    sn=-1;
    for(int x=0;x<=N;x++) bt[x]=-1;
    recur("",0,0);
    cout<<solve;
}