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

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

 

 

코드

def solution(numbers,cnt):
    global result
    
    # 숫자를 저장할 빈 문자열 생성
    tmp = ''
    for number in numbers:
        tmp += number
        
    # 이 교환횟수에서 이미 만들어진 적 있는 숫자라면 리턴해서 실행시간 단축
    if int(tmp) in result[cnt]:
        return
    # 처음 만들어진 숫자라면 정수형으로 바꿔서 리스트에 추가
    else:
        result[cnt].append(int(tmp))
    
    # 교환횟수를 다 소진했다면 리턴
    if cnt==0:
        return
    
    length = len(numbers)
    
    # 두 숫자의 자리를 교환하고 dfs 탐색을 진행한 뒤 원상복구
    for i in range(length):
        for j in range(i+1,length):
            numbers[i],numbers[j] = numbers[j],numbers[i]
            solution(numbers,cnt-1)
            numbers[i],numbers[j]=numbers[j],numbers[i]

T = int(input())

for test_case in range(1, T + 1):
	# 숫자와 교환횟수를 입력받음
    n, chance = input().split()
    # 자리수교환을 편하게 하기 위해서 리스트로 변경함
    numbers = list(n)
    # 남은 교환횟수별로 만들어진 숫자를 저장하는 리스트 생성
    result = [[] for _ in range(int(chance)+1)]
    
    solution(numbers,int(chance))
    # 교환횟수를 모두 소진했을 때 만든 숫자 중 가장 큰 것을 출력
    print('#{} {}'.format(test_case,max(result[0])))

 

후기

• 남은 교환횟수를 깊이로 DFS 탐색을 해서 풀어내는 것이 인상적이었다.