[SWEA] 최대 상금 - python

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

SW Expert Academy

 

DFS를 잘 사용할 수 있는지 테스트하는 문제.

n과m 시리즈를 잘 풀었다면 무난하게 풀었을 것 같다.

 

상태트리를 생성해

for문으로 계속해서 원소들을 교환하면서 k값에 넣어서 최대값을 뽑아낸다.

참고로 아래 코드는 가지치기를 진행하지 않아 효율성 검사에서 실패하므로 가지치기를 진행해주면 해결된다.

T = int(input())

def DFS(L, k):
    global answer
    if L == b:
        if answer < k:
            answer = k
    else:
        for i in range(len(a)):
            for j in range(i+1, len(a)):
                tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
                swap = int("".join(map(str, arr)))
                if k < swap:
                    k = swap
                DFS(L+1, k)
                tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp

for _ in range(T):
    answer = 0
    arr = []
    a, b = map(int, input().split())
    a = str(a)
    for i in a:
        arr.append(i)
    DFS(0, 0)
    print(f'#{_+1} {answer}')

 

완성