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

[URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

SW Expert Academy

[풀이 과정]

재귀 완전 탐색

 

첫번째 시도.(실패)

각각 N번의 경우마다 최상을 찾아감 -> 각각의 경우 중 최선이지만, 최종 안되는 경우가 생김

 

두번째 시도.

전체 (N번 * 경우의수) 중 제일 큰 값을 찾는다.

 

현재의 위치: cur를 기준

오른쪽을 탐색하며  오른쪽값이 큰 숫자이면 swap

swap경우 cnt++ 하여 재귀로 탐색 dfs()

 

 

[소스 코드]

 

#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
 
char input[10];
string s;
int N;
int dap;
 
void dfs(int cur, int cnt) {
    if (cnt == N)
    {
        // 재귀로 N번까지 탐색 완료
        dap = max(dap, stoi(s));        // 구한 문자열 중 가장 큰 값을 dap 으로!
        return;
    }
 
    for (int i = cur; i < s.size(); i++)
    {
        for (int j = i + 1; j < s.size(); j++)
        {
            if (s[i] <= s[j]) {        // (앞자리 수 <= 뒤자리 수) 바꿔주고 가능한 경우 -> 완전 탐색!
 
                swap(s[i], s[j]);
 
                dfs(i, cnt + 1);
                
                swap(s[i], s[j]);
            }
        }
    }
}
 
 
int main() {
    int T;
    scanf("%d", &T);
 
    for (int tc = 0; tc < T; tc++)
    {
        scanf("%s", input);
        s = input;
 
        scanf("%d", &N);
 
        dfs(0, 0);
 
        printf("#%d %d\n", tc + 1, dap);
    }
 
    return 0;
}