⏹️[SW Expert Academy] [Python] [D3] [1244] 최대 상금

문제

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

SW Expert Academy

풀이

이 문제는 백트래킹 문제이다. 완전탐색으로 풀게되면 시간초과가 발생한다.  DFS를 이용해 탐색하면서 가지치기를 해주면된다. 먼저 모든 경우의 수를 확인해야 하기 때문에 2중 for문을 돌게 된다. 이 때 방문했던 것을 체크하지 않으면 시간초과가 발생한다. 

# 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 
def dfs(n):
    global result
    if n == N:
        result = max(result, int("".join(map(str, num))))
        return 
    for i in range(L-1):
        for j in range(i+1, L):
            num[i], num[j] = num[j], num[i]

            check = int("".join(map(str, num)))
            if (n, check) not in visited:
                dfs(n+1)
                visited.append((n, check))

            num[j], num[i] = num[i], num[j]

T = int(input())

for test_case in range(1, T + 1):
    st, t = map(str, input().split())
    num, visited = [], []
    N = int(t)
    L = len(st)
    result = 0

    for i in st:
        num.append(i)
    dfs(0)
    print("#{} {}".format(test_case, result))

 

Java 코드

package SWEA;

import java.util.Scanner;

public class SW_1244 {
    static String[] arr;
    static int max, chance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int test_case = 1 ; test_case <= T ; test_case++) {
            arr = sc.next().split("");
            chance = sc.nextInt();

            max = 0;

            if(arr.length < chance) {
                chance = arr.length;
            }
            dfs(0, 0);
            System.out.println("#" + test_case + " " + max);
        }
    }
    static void dfs(int start, int cnt) {
        if(cnt == chance) {
            String result = "";
            for(String s : arr)
                result += s;
            max = Math.max(max, Integer.parseInt(result));
            return;
        }
        for(int i = start; i < arr.length; i++) {
            for(int j = i + 1; j < arr.length; j++) {
                // swap
                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;
            }
        }
    }
}