[C++] SWEA 1244번: 최대상금

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

완전 탐색으로 돌려줬다.

완전 탐색 문제를 풀 때는 조건문으로 필요없는 반복을 줄이는 것이 중요하다.

 

for문으로 교환해줄 때 i, j의 조건을 보자.

j는 i보다 더 큰 수로만 증가하여 중복되는 교환횟수를 줄였다.

 

visited[ 교환 후 숫자 ] [교환횟수] 로 중복 교환 횟수를 줄여주었다.

 

💾  소스

#include <iostream>
#include <string>
#include <memory.h> // memset
#include <algorithm> // swap

#define MAX 1000000
 
std::string answer;
bool visited[MAX][11]; // [숫자][교환횟수]
 
void solve(std::string& s, int depth)
{
    if (depth == 0)
    {
        if (s > answer)
            answer = s;
        return;
    }
 
    for (int i = 0; i < s.length()-1; i++)
    {
        for (int j = i+1; j < s.length(); j++)
        {
            std::swap(s[i], s[j]);
            if(!visited[std::stoi(s)][depth])
            {
                visited[std::stoi(s)][depth] = true;
                solve(s, depth-1);
            }
            std::swap(s[i], s[j]);
        }
    }
}
 
 
int main()
{
    int T = 0; std::cin >> T;
    for (int tc=1; tc<=T; ++tc)
    {
        answer = "";
	    	std::string str = "";
        memset(visited, false, sizeof(visited));

        int cnt;
        std::cin >> str >> cnt;
        
        solve(str, cnt);
        
        std::cout << '#' << tc << ' ' << answer << '\\n';
    }
 
    return 0;
}