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

🫠문제

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

SW Expert Academy

숫자들의 주어진 수 만큼 교환하여 가장 큰수를 만드는 문제이다

 

 

😎풀이

백트레킹으로 해결했다

• (해당 회차, 숫자리스트) 로 visited 여부를 확인하고 같은 것이 반복되지 않도록했다
• combinations를 이용해서 가능한 교환의 경우를 계산하고 이를 순회한다

from itertools import combinations

def Backtracking(n):
    global answer
    
    if n == change:  # 모두 회전한 경우
    	result = 0
        for num in range(len(num_list)):
            result = result * 10 + num_list[num]
        answer=max(answer,result)
        return

    for comb in combs:
        i,j=comb
        num_list[i],num_list[j]=num_list[j],num_list[i]
        for num in range(len(num_list)):
            result = result * 10 + num_list[num]
        if (n,result) not in visited:
            Backtracking(n + 1)
            visited.add((n,result))
        num_list[j], num_list[i] = num_list[i], num_list[j] # 백트레킹의 핵심


T = int(input())
for t in range(T):
    num, change = map(str, input().split())
    num_list = list(map(int, num))
    len_num_list=len(num_list)
    change = int(change)
    index_list = list(i for i in range(len(num_list)))
    combs = list(combinations(index_list, 2))
    visited=set()
    n = 0
    Backtracking(0)
    print(f"#{t+1} {answer}")