[SWEA/Python] 1244. 최대 상금

📌 문제

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

SW Expert Academy

 

📌 문제 접근 방법

1. 앞 쪽에 위치한 숫자판보다 큰 숫자가 뒷쪽에 있다면 그 둘을 바꾸는 방법
   → 32888 같은 경우에 틀리게 된다.
2. 모든 경우의 수를 다 찾아서 비교해보자! → 재귀로 구현했으나 시간초과!
3. 가지치기가 가능한가?
   
   • 뒷 쪽 숫자가 더 클 경우에만 교환을 하는 방식
   • 교환 횟수에 따라 따로 리스트에 값을 저장하여 중복을 방지
   • 두 번째 경우엔 시간 초과없이 값이 잘 나왔다!

 

📌 코드

import sys
sys.stdin = open('input.txt')

def change(numbers, cnt):
    global result

    temp = ''
    for number in numbers:
        temp += number
    
    if int(temp) in result[cnt]:
        return
    else:
        result[cnt].append(int(temp))

    if cnt == 0:
        return

    n = len(numbers)

    for i in range(n):
        for j in range(i+1, n):
            numbers[i], numbers[j] = numbers[j], numbers[i]

            change(numbers, cnt-1)

            numbers[i], numbers[j] = numbers[j], numbers[i]


T = int(input())

for t in range(1, T+1):
    temp, cnt = input().split()

    numbers = list(temp)
    result = [[] for _ in range(int(cnt)+1)]

    change(numbers, int(cnt))

    print('#{} {}'.format(t, max(result[0])))