(SWEA c++)1244. [S/W 문제해결 응용] 2일차 - 최대 상금

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy

완전탐색을 이용한 문제 풀이.

 

전역변수로 string형 s로 숫자를 입력 받고, int형 변수 change에 교환 횟수를 저장한다.

또한 ans를 통해 정답을 저장하면서 비교하도록 한다.

 

dfs를 통해 완전탐색을 진행한 후 교환횟수에 다다랐을 때 현재 값과 ans에 저장해 놓은 수를 비교하여 더 큰 수를 ans에 저장한다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int ans, change;
string s;

void dfs(int index, int current)
{
    if(current == change)
    {
        ans = max(ans, stoi(s));
        return;
    }
    for(int i = index; i < s.size() - 1; i++)
    {
        for(int j = i + 1; j < s.size(); j++)
        {
            swap(s[i], s[j]);
            dfs(i, current + 1);
            swap(s[i], s[j]);
        }
    }
}

int main(void)
{
    int t;
    cin >> t;
    
    for(int i = 1; i <= t; i++)
    {
        cin >> s >> change;
        ans = 0;
        
        if(change > s.size())
            change = s.size() - 1;
        dfs(0, 0);
        cout << "#" << i << " " << ans << endl;
    }
    return 0;
}