[SWEA] 1244번 최대상금

1244 최대상금

풀이)

교환할 수 있는 모든 경우를 확인해서 최대값을 찾았다.

입력값을 int형으로 받아 자릿수대로 배열에 저장해놓고,

바꾼 다음 다시 원래대로 만들어 놓기 귀찮아서

아예 입력값을 string으로 받았다

string 입력값을 순서를 바꾼 뒤 stoi()함수를 통해 int형으로 바꿔 최대값인지 확인해줬다. 

주의

값이 큰 수가 제일 앞에 있어야 하므로

자리를 바꿀 때, 뒤의 자리값이 클 경우에만 교환해줬다.

코드)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include<string.h>
using namespace std;
 
string s;
int n;
int result;
 
void dfs(int idx,int cnt) {
    
    if (cnt == n) {
        result = max(result, stoi(s));
        return;
    }
    if (idx >= s.length())return;
    for (int i = idx; i < s.length(); i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s[i] <= s[j]) {
                swap(s[i], s[j]);
                dfs(i, cnt + 1);
                swap(s[i], s[j]);
            }
        }
    }
}
int main() {
    //freopen("input.txt", "r", stdin);
    int test_case=0;
    int T=0;
    scanf("%d", &T);
    for (test_case = 1; test_case <= T; test_case++) {
        cin >> s >> n;
        result = stoi(s);
        //printf("%d", s.length());
        dfs(0, 0);
        printf("#%d %d\n", test_case,result);
    }
    return 0;
}

예를 들어 입력값이 78644 2이면