[SWEA] 1244번 최대상금 자바 풀이(그리디X 완전탐색O)

sw expert academy 1244 최대 상금 문제 자바(java) 풀이

• 난이도 : D3
• sw expert academy 1244 최대 상금
  
  
  

문제정리

1. 숫자판이 주어질때 정해진 횟수내에서 서로의 자리를 교환할 수 있다.
2. 숫자판의 위치에 따라 가중치가 부과된다. (오른쪽 끝이 1원, 왼쪽으로 갈수록 10의 배수로 커진다.)

• 반드시 정해진 횟수만큼 교환을 해야한다. 동일한 위치의 교환이 중복되어도 된다.

3. 정해진 숫자만큼 교환을 진행했을때 가장 큰 금액을 계산해라
   
   
   

문제풀이

이 문제는 greedy로 풀 수 없습니다. greedy로 풀게되면 답이 나오는 것도 있지만 안나오는 경우도 있습니다.
그러므로 모든 경우를 탐색해야 합니다. 모든 경우를 탐색하기 위해 자리를 모두 바꿔봅니다.

1. dfs 함수를 통해 가능한 모든 자리 바꿈을 진행합니다.
   순열을 구할때 뒤의 값(오른쪽의 값)이 더 큰 경우에만 swap 하도록 합니다.
   왼쪽에 있는 값이 더 크다면 오른쪽에 있는 값과 바꾸는 것은 의미 없기 때문입니다.
2. 주어진 이동 횟수 만큼 이동이 끝나면 string으로 변환하고, 숫자로 변환하여 최대 값을 갱신합니다.
   
   
   

swea 1244번 최대 상급 자바 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.IOException;

class Solution {    
    static int num, move;
    static int[] arr;
    static String str = "";
    static int result;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            String[] temp = br.readLine().split(" ");
            move = Integer.parseInt(temp[1]);

            arr = new int[temp[0].length()];
            String[] temp2 = temp[0].split("");

            for(int i=0; i<arr.length; i++){
                arr[i] = Integer.parseInt(temp2[i]);
            }
            result = 0;
            dfs(0,0);
            bw.write("#" + test + " "+ result);
            bw.newLine();
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int k, int cnt){
        int t;
        if(cnt == move){
            str = "";
            Arrays.stream(arr).forEach(x -> str += String.valueOf(x));  // 문자로 변환
            result = Math.max(result, Integer.parseInt(str));   // 숫자로 변환하여 값 비교
            return;
        }
        // 뒤의 값들과 차례차례 바꿔 나가며 모든 경우 조사
        for(int i=k; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                if(arr[i] <= arr[j]){
                    t = arr[i]; arr[i] = arr[j]; arr[j] = t;    // swap
                    dfs(i, cnt + 1);
                    t = arr[i]; arr[i] = arr[j]; arr[j] = t;    // 원래 자리로 돌려놓기

                }
            }
        }
    }
}