문제 링크

문제 링크

문제 요약

수열에서 두 개의 수를 골라 N회 변경해서 최대값을 만들자.

문제 풀이

DFS로 모든 경우를 시도한다.
이미 시도한 경우를 저장해서 중복된 접근을 생략한다.

DFS(N^2)

def swap(a, b):
    return b, a
 
 
def arr_to_int(arr):
    return int("".join(arr))
 
 
def dfs(arr, remain):
    global answer
    if remain == 0:
        num = arr_to_int(arr)
        answer = max(answer, num)
        return
 
    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            arr[i], arr[j] = swap(arr[i], arr[j])
 
            num = arr_to_int(arr)
            if num not in save[remain]:
                dfs(arr, remain - 1)
                save[remain].add(num)
 
            arr[i], arr[j] = swap(arr[i], arr[j])
 
 
T = int(input())
for test_case in range(1, T + 1):
    global answer
    answer = 0
    arr, count = input().split()
    arr = list(arr)
    count = int(count)
    save = {k: set() for k in range(count+1)}
 
    dfs(arr, count)
    print(f"#{test_case} {answer}")