SWEA 1244 최대상금

import java.util.Scanner;

public class Max_Prize {
    static int[] arr;
    static int change;
    static int len;
    static int max;
    public static void main(String args[]) throws Exception
    {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            String str = sc.next();
            change = sc.nextInt();
            len = str.length();
            arr = new int[len];
            for(int i  =0; i<len; i++){
                arr[i] = str.charAt(i)-'0';
            }
            max =0;
            dfs(0,0);
            System.out.println("#" + test_case+" "+max);
        }
    }
    public static void dfs(int start, int count){
        if(count == change){
            int num = 0;
            for(int i = 0; i<len; i++){
                int cnt = 1;
                for(int j = 1; j<len-i; j++){
                    cnt = cnt*10;
                }
                num += cnt*arr[i];
            }
            max = Math.max(max,num);
            return;
        }
        for(int i = start ; i<len; i++){
            for(int j =i+1; j<len; j++){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                dfs(i,count +1);
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

풀이방법

두개를 바꾸는 모든 경우의 수를 찾고 경우의 수 중 최댓값을 찾는다
dfs함수 안에 이중포문 안에 인덱스가 풀이의 핵심이다.

1. 첫번째 수 부터 한개씩 바꿔보고 count를 증가시켜 재귀함수를 호출한다.
2. count값이 교환횟수랑 같다면 max값을 통해 최댓값을 비교한다.
3. dfs탐색이 끝나면 원상복구 시켜준다.

후기

start값을 통해 현재 교환하는 숫자를 같이 넘겨줘야 한다.
이부분을 해결하지 못해서 무한루프가 발생했던거 같다.