[SW Expert Academy] 최대 상금 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=%EC%B5%9C%EB%8C%80+%EC%83%81%EA%B8%88&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

아래 숫자 조작 문제의 심화 버전이라는 느낌을 받았다.

먼저 공부해보고 풀면 좋을 것 같다.

 

시간 제한은 20초이긴 하지만 지금 거의 10초 가까이 나오기 때문에

가지치기 하는 방법을 더 생각해보면 좋을 것 같다.

import java.util.Scanner;

class Solution {

	public static int n, max;
	public static char arr[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {

			max = Integer.MIN_VALUE;

			String num = sc.next();

			arr = num.toCharArray();

			n = sc.nextInt();

			dfs(0, 0);

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

	}

	public static void dfs(int pos, int cnt) {
		if (cnt == n) {
			int num = Integer.parseInt(new String(arr));
			max = Math.max(num, max);
			return;
		}

		for (int i = pos; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				swap(i, j);
				dfs(i, cnt + 1);
				swap(i, j);
			}
		}
	}

	public static void swap(int i, int j) {
		char tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}