최대상금 Python(SW Expert Academy)

난이도 : D3

문제번호 : 1244

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다. 우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다. 정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다. 숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다. 위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다. 여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다. 정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

 

 

 

입력

가장 첫 줄은 전체 테스트 케이스의 수이다. 최대 20개의 테스트 케이스가 표준 입력을 통하여 주어진다. 각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다. 숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

출력

각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다. 같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

예시

입력	출력
3 123 1 2737 1 32888 2 . . .	#1 321 #2 7732 #3 88832 . . .

---

2. 문제풀이

D3 치고는 어려운 문제라고 생각했다. 완전탐색으로 풀려고 하면 시간초과가 생기기때문에 백트래킹, 가지치기 작업이 필요하다. 제가 여기서 생각했던 가지치기는 '같은 교환회수일때 이미 나온 수라면 넘아가자' 다. 이러한 정보를 딕셔너리를 이용하여 저장해 문제를 풀어나갔다.

---

3. 소스코드

 

#D3 1244 최대상금
 
#경우의 수 찾기, 매개변수로 몇번 바꿧는지 적는다.
def dfs(count):
    global answer
    #횟수를 다 사용했다면
    if not count:
        #숫자로 바꿔보고
        temp = int(''.join(values))
        #가지고 있는 최대수보다 크다면 갱신
        if answer < temp:
            answer = temp
        return
    # 바꿔야 하니까 이중 포문
    for i in range(length):
        #경우의 수를 찾는거니까 i보다 큰위치부터
        for j in range(i+1, length):
            #두개의 위치를 바꾸고 나서
            values[i], values[j] = values[j], values[i]
            #가지치기 해야하니까 일단 합쳐보고
            temp_key = ''.join(values)
            #어떤수가 몇회차에 나왔는지 체크 1이면 안나온거니까 경우의수에 넣어주기
            if visited.get((temp_key, count-1), 1):
                #이숫자는 몇회차에 사용했으니까 체크해주고
                visited[(temp_key, count-1)] = 0
                #dfs도 돌려주고
                dfs(count-1)
            #다 썻으면 원상복귀
            values[i], values[j] = values[j], values[i]
 
 
for t in range(int(input())):
    answer = -1
    value, change = input().split()
    #바꾸기 편하려고 리스트화시킴
    values = list(value)
    change = int(change)
    #계속 쓸꺼니까 캐스팅
    length = len(values)
    #가지치기용 딕셔너리
    visited = {}
    dfs(change)
    print('#{} {}'.format(t+1, answer))