1244 최대 상금

최대 상금

Solution

import java.io.*;
import java.util.*;

class SW1244 {
	static String[] arr;
	static int chance, answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr = st.nextToken().split("");
			chance = Integer.parseInt(st.nextToken());
			answer = 0;
			
			if (arr.length < chance) {
				chance = arr.length;
			}
			
			dfs(0, 0);
			System.out.println("#" + t + " " + answer);
		}
	}
	
	static void dfs(int idx, int cnt) {
		if (chance == cnt) {
			String result = "";
			for (String s : arr) {
				result += s;
			}
			answer = Math.max(answer, Integer.parseInt(result));
			return;
		}
		
		for (int i = idx; i < arr.length-1; i++) {
			for (int j = i+1; j <arr.length; j++) {
				
				String temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				
				dfs(i, cnt+1);
				
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

배운점

가장 먼저 시간초과 방지 조건으로 교환 횟수가 입력받은 문자열의 길이보다 큰 경우엔 문자열 길이 만큼만 반복하도록 하였다.

dfs의 탈출조건으로 교환횟수랑 cnt가 같을 때 문자열을 정수형으로 변환하고 최대값을 answer에 넣어준다.

그렇지 않은 경우엔 이중 for문을 돌며 idx를 기준으로 idx 이후의 문자열과 교환해 주고 cnt를 증가시키며 확인한다.
그러고 교환을 다시 초기화 해 주는 백트래킹 방식이다.