SWEA 1244 최대상금 JAVA

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

문제 링크

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

SW Expert Academy

 

처음에 제일앞에 큰 숫자가 오는 방향으로 이중 for문으로 구현하였으나 시간초과가 떴고

이를 보완하여 dfs를 이용한 완전탐색을 구현하였다.

 

또한 그렇게구현하였는데

모든 테스트 케이스를 통과 하지 못하였다.

 

확인해 보니 dfs() 메소드의 return을 하는 if문에 걸리지 않기 때문이란것을 알게되었는데

주어진 숫자판과 교환가능 횟수를 비교 하였을때 교환가능 횟수가 숫자판의 자릿수보다 크다면

걸리지 않았다 왜냐하면 for문에서 숫자판의 길이만큼까지만 가는데 count가 n이 될수 없는것이다;;

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    static int max;
    static int[] moneyInt ;
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T= Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            max = Integer.MIN_VALUE;
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            String money = st.nextToken();
            moneyInt = new int[money.length()];
            n = Integer.parseInt(st.nextToken());
            for(int i =0;i<money.length();i++){
                moneyInt[i] = Character.getNumericValue(money.charAt(i));
            }

            if (moneyInt.length < n) {
                n = moneyInt.length;
            }
            dfs(0,0);
            sb.append("#").append(test_case).append(" ").append(max).append("\n");

        }
        System.out.println(sb);
    }
    public static void dfs(int start, int count ){
        if(count == n){
            StringBuilder st = new StringBuilder();
            for(int a : moneyInt){
                st.append(a);
            }
            max = Math.max(max, Integer.parseInt(st.toString()));
            return;
        }
        for (int i = start; i < moneyInt.length; i++) {
            for (int j = i + 1; j < moneyInt.length; j++) {
                int tmp = moneyInt[i];
                moneyInt[i] = moneyInt[j];
                moneyInt[j] = tmp;

                dfs(i,count +1);

                tmp = moneyInt[i];
                moneyInt[i] = moneyInt[j];
                moneyInt[j] = tmp;
            }
        }
    }
}