[swea 1244-파이썬][S/W 문제해결 응용] 2일차 - 최대 상금

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

사용언어 : PYTHON

풀이

구현을 위한 생각

---

백트래킹을 사용하여 모든 경우를 중복없이 탐색한다.

모든 경우를 탐색하며 goal(주어진 숫자를 내림차순으로 정렬한 값)과 차이가 가장 작은 값이 정답이다.

💡 goal : 이동횟수 제한이 없다고 할 때, 숫자를 swap해서 도달할 수 있는 최대값은 내림차순으로 정렬한 값이다.

백트래킹

---

숫자카드 1,2,3,4가 있다고 할 때 두 번 교환할 수 있는 모든 경우는 위 그림과 같다.
(x표시는 중복되는 경우)

바로 직전에 교환한 경우보다 뒤의 경우만 조회하면 중복없이 교환할 수 있다.

바로 직전에 교환한 경우를 기억하기 위해서 stack을 활용하였다.

코드

def backTracking(m):
    global answer

    if m==n: # n번 교환한 경우 도달할 base case
        result=goal-int(''.join(l)) # goal값과 숫자를 교환한 값의 차이를 구함

        if result < answer: # 최솟값을 갱신
            answer=result

        return


    for i in range(0,len(l)-1):
        for j in range(i+1,len(l)):
            a,b=chk[-1] # 바로 직전에 교환한 카드 a,b
            if (i>=a and j>=b) or i>a: # 직전 경우를 활용하여 중복 제거 

                l[i],l[j]=l[j],l[i] # 교환
                chk.append([i,j]) # stack에 교환한 카드 push

                backTracking(m+1) # recursion으로 백트레킹하여 모든 경우를 탐색한다

                l[i],l[j]=l[j],l[i] # 탐색이 끝나면 교환했던 카드를 원상복구
                chk.pop() # stack 원상복구

                if answer==0: # 만약 answer이 0이라면 정답을 찾은 경우이므로 더이상 backtracking을 할 필요가 없다
                    return

T=int(input())



for i in range(T):

    l,n=map(int,input().split())
    l=list(str(l))
    goal=int(''.join(sorted(l,reverse=True)))
    answer=999999 # 6자리 중 가장 큰 값 999999(문제에서 최대 자릿수는 6으로 주어짐)
    chk=[[-1,-1]] # 바로 직전의 교환한 카드들을 기억하기위한 stack

    backTracking(0)

    print('#{} {}'.format((i+1),goal-answer))