[SWEA D3] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금]

문제 : [SWEA D3] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

풀이

def dfs(idx, cnt):
    global answer
    if cnt == n: # 교환 수를 다 채운 경우
        answer = max(int("".join(nums)), answer) # answer에 저장된 값과 nums에 있는 값을 비교해서 큰 값을 answer로 지정
        return
    for i in range(idx, count):
        for j in range(i + 1, count):
            if nums[i] <= num[j]: # 뒤에 있는 값이 앞에 있는 값보다 크면 교환
                nums[i], nums[j] = nums[j], nums[i]
                dfs(i, cnt + 1)
                nums[i], nums[j] = nums[j], nums[i] # 원상 복구
    if not answer and cnt < n: # 실행 중간에 나올 수 있는 가장 큰 수가 나온 경우
        if (n - cnt) % 2 == 1: # 홀수이면 마지막 두 자리만 교환, 짝수이면 변화 없음
            nums[-1], nums[-2] = nums[-2], nums[-1]
        dfs(idx, n)

T = int(input())
for t in range(1, T + 1):
    num, n = input().split()
    nums = list(num)
    count = len(nums)
    n = int(n)
    answer = 0
    
    dfs(0, 0)
    print(f"#{t} {answer}")