1244. 최대 상금 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

def dfs(cnt):
    global ans
    if cnt==C:
        s_num=int(''.join(N))
        ans=max(ans,s_num)
        return

    for i in range(len(N)-1):
        for j in range(i+1,len(N)):
            N[i],N[j]=N[j],N[i]
            if (cnt+1,''.join(N)) not in N_set:
                N_set.add((cnt+1,''.join(N)))
                dfs(cnt+1)
            N[i],N[j]=N[j],N[i]
            
T = int(input())

for test_case in range(1, T + 1):
    N,C=input().strip().split()
    C=int(C)
    N=list(N)
    ans=0
    N_set=set()
    dfs(0)
    print(f'#{test_case} {ans}')

• dfs를 사용하여 완전탐색을 한다.
• 이 때 N=6, C=10이기 때문에 시간초과가 발생할 수 있다.
• 따라서 N_set에 횟수와 숫자를 저장하여 중복된 변경을 하지 않도록 하여 시간초과를 피했다.