[JAVA] SWEA (D3) 1244. 최대 상금

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=1

---

문제 설명

(정답률 36.27%)
정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

---

입력 예제

3
123 1
2737 1
32888 2

---

출력 예제

#1 321
#2 7732
#3 88832

---

정답 코드

dfs를 이용한다.
32888을 2번 교환하는 경우를 예를 들면
각 자리씩 1번 교환하는 경우 다음과 같고

• 3을 교환
  23888 -> 2번째 교환: 28388, 28838, 28883
  82388
  82838
  82883
• 2를 교환
  38288
  38828
  38882
• 8(32888)을 교환
  32888
  32888
• 8(32888)을 교환
  32888

여기서 각각의 반복문에서 재귀를 호출하여 최대값일 경우를 계산한다.
깊이가 주어진 교환 횟수가 됐을 경우 재귀를 중단한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class SWEA {

    static String[] reward;
    static int swapCount;
    static int max;
    static String newReward;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input (8).txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int test_case = 1; test_case <= T; test_case++) {

            st = new StringTokenizer(br.readLine());
            //교환전 상금
            reward = st.nextToken().split("");
            //교환 횟수
            swapCount = Integer.parseInt(st.nextToken());
            //최대값 초기화
            max = 0;

            //최대 자릿수 이상일 경우
            if (swapCount > reward.length) {
                swapCount = reward.length;
            }

            dfs(0, 0);

            System.out.println("#" + test_case + " " + max);
        }
    }

    private static void dfs(int start, int depth) {
        //깊이가 교환 횟수일 때 기존 최대값과 비교 후 갱신
        if (swapCount == depth) {
            newReward = String.join("", reward);
            max = Math.max(max, Integer.parseInt(newReward));
            return;
        }
        //이중 for문으로 구성하여 모든 경우 체크
        for (int i = start; i < reward.length - 1; i++) {
            for (int j = i + 1; j < reward.length; j++) {
            	//상금 교환
                String temp = reward[i];
                reward[i] = reward[j];
                reward[j] = temp;
				//교환한 상금으로 재귀 호출
                dfs(i, depth + 1);
				//교환 취소
                temp = reward[i];
                reward[i] = reward[j];
                reward[j] = temp;
            }
        }
    }
}

---

정리

백트래킹을 이용한 dfs나 bfs는 아직 익숙치 않아서 어려웠다.