[SWEA] 1244. 최대 상금

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

DFS를 이용해 풀었다.

단순 비교에 배열을 합해야 하는 경우가 있어 int 배열보단 char 배열로 저장하는 게 더 편했다.

왼쪽 수보다 오른쪽 수가 더 크거나 같을 경우 (체크 - 교환 - 재귀 - 교환) 했다.

check는 이번 깊이 탐색에 교환이 있었는지를 나타내며, 다른 깊이 탐색도 고려해 매번 윗줄에 check를 초기화해야 했다.

교환이 없었다면, 완벽히 정렬되어 짝수 번 혹은 홀수 번이 남은 상황이며

짝수일 경우 바로 제거, 홀수일 경우 맨끝의 두 수를 swap한 후 제거했다. 

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int num_length, mx;
    static char[] m;
     
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
        for(int tc = 1; tc <= T; tc++) {
            String num = sc.next();
            num_length = num.length();
            mx = 0;
            m = num.toCharArray();
            int cg = sc.nextInt();
             
            bfs(0, cg);
            System.out.println("#" + tc + " " + mx);
        }
    }
     static void bfs(int idx, int cnt) {
        if(cnt == 0) {
            String s = String.valueOf(m);
            mx = Math.max(mx, Integer.valueOf(s));
            return;
        }
        boolean check = false;
        for(int i=idx; i<num_length; i++) {
            for(int j=num_length-1; j>i; j--) {
                if (m[i]-'0' <= m[j]-'0') {
                    check = true;
                    swap(i, j);
                    bfs(i, cnt-1);
                    swap(i, j);
                }
            }
        }
        if(!check) {
            if(cnt%2 ==1) {
                swap(num_length-1, num_length-2);
                bfs(num_length-1, 0);
                swap(num_length-1, num_length-2);
            }
            else {
                bfs(num_length-1, 0);
            }
        }
    }
    static void swap(int a, int b) {
    	char temp = m[a];
        m[a] = m[b];
        m[b] = temp;
    }
}