[swexpert] 1244. 최대 상금 (완전탐색, C++)

최대 6자리 숫자의 자리수 중에 2개를 고르는 것: 6C2 =15가지 

 최대 10번 자리 교환한다 15의 10승=> 시간초과

따라서 VISIT방문 처리를 해주거나 다른 방법으로 풀어야되는데 다른 사람걸 보고

VISIT[만든숫자][교환횟수]=TRUE 

 

이런식으로 해주면 된다. 백준의 토마토 3차원문제가 이런식으로 했던거 같은데 가끔 잊을만하면 나온다

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;
int result;
bool visit[1000000][11];

int toNumber(string s){
	int temp=0;
	for(int i=0;i<s.size();i++){
		temp=temp*10+s[i]-'0';
	}
	return temp;
}

void dfs(string tmp,int cnt){
	
	if(cnt==0){
		int temp=toNumber(tmp);
		if(temp>result)result=temp;
		return;
	}


	for(int i=0;i<tmp.size();i++){
		for(int j=i+1;j<tmp.size();j++){
			swap(tmp[i],tmp[j]);
			if(visit[toNumber(tmp)][cnt]==false){
				visit[toNumber(tmp)][cnt]=true;
				dfs(tmp,cnt-1);
			}
			
			swap(tmp[i],tmp[j]);
		}
	}
	
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t,count;
	string num;
	cin>>t;
	for(int tc=1;tc<=t;tc++){
      	cin>>num>>count;//정보판,교환 횟수
      	result=0;
		memset(visit,false,sizeof(visit));
       
        dfs(num,count);
      
		cout<<"#"<<tc<<" "<<result<<"\n";
		
	}

	
	return 0;
}