SWEA 1244. 최대 상금(Python)

dfs를 이용해 완전탐색한 문제다.
i번째와 j번째의 숫자를 위치를 바꿔주고, 만약 (바꾼 숫자만큼의 상금,바꾼횟수)이 이미 존재하면 중복된 경우므로 패스하고 다시 원상복구한다.
그리고 바꾼횟수가 C와 같아지면 ans=max(tmp,ans), 혹은 처음 주어진 상금숫자에서 최대값과 현재 tmp에 담긴 상금이 같을시, 남은 횟수가 2의 배수인경우 즉시 종료.
최대값과 tmp의 값이 같고 남은 횟수가 2의 배수가 아닌경우, 최대값에서 맨뒤의 2개값만 바꾸면 될 것 같은데 계속 오류가 발생;;

res=[]
def change(count):
    global C,ans,tmp
    if count==int(C):
        tmp=''.join(S)
        ans=max(int(tmp),int(ans))
        return
    if int(tmp)==int(maxval):
        if (int(C)-count)%2==0:
            ans=maxval
        #else:  요부분은 이상하게 에러가 발생
        #    ans=maxval[:-2]+maxval[-1]+maxval[-2]
        return
    for i in range(N):
        for j in range(i+1,N):
            S[i],S[j]=S[j],S[i]
            tmp=''.join(S)
            if (tmp,count) not in dic:
                dic[(tmp,count)]=1
                change(count+1)
            S[i],S[j]=S[j],S[i]
    
for m in range(int(input())):
    ans,tmp="0","0"
    S,C=map(str,input().split())
    S=list(S)
    N=len(S)
    maxval=''
    dic={}
    for i in sorted(S,reverse=True):
        maxval+=i
    change(0)
    res.append(ans)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))