[SWEA][Python] 1244 최대상금

뒤쪽의 큰값을 찾아 교환하며 탐색한 후 혹시 이미 내림차순 정렬이 완료됐는데 교환 횟수를 소모하지 못했을 경우

홀수면 맨뒤 두개 교환, 짝수면 그대로 반환시킨다.

 

def dfs(idx, cnt):
    global answer
    if cnt == int(target):
        answer = max(int("".join(nums)), answer)
        return
    for now in range(idx, n):
        for max_idx in range(now + 1, n):
            if nums[now] <= nums[max_idx]:
                nums[now], nums[max_idx] = nums[max_idx], nums[now]
                dfs(now, cnt + 1)
                nums[now], nums[max_idx] = nums[max_idx], nums[now]
    if not answer and cnt < int(target):
        rotate = (int(target) - cnt) % 2
        if rotate:
            nums[-1], nums[-2] = nums[-2], nums[-1]
        dfs(idx, int(target))


for test in range(1, int(input()) + 1):
    nums, target = input().split()
    n = len(nums)
    nums = list(nums)
    answer = 0
    dfs(0, 0)
    print(f'#{test} {answer}')