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

문제

풀이

입력으로 받은 숫자를 반드시 M번 교환한 후, 가장 큰 수를 출력하는 문제이다.

입력으로 들어오는 수의 최대 값은 999,999 이고, 최대 교환 가능 횟수는 10회이다.

즉, $_6C_2^{10} = 15^{10}$ 으로 엄청난 연산 횟수가 발생한다.
모든 경우의 수를 탐색하는 브루트 포스 방법은 적용할 수 없다.
그렇다면, 불필요한 경우의 수를 제거하여 연산 횟수를 줄여야 한다.

만약, 입력으로 999,999 와 10이 들어왔다면 0번째 9와 1번째 9를 서로 교환하는 것과, 0번째 9와 2번째 9를 서로 교환하는 경우는 동일한 교환 횟수에 동일한 결과 값이 나올 것이다.

여기서 불필요한 연산을 제외할 수 있는 것이다. (교환 횟수, 숫자)를 하나의 집합으로 묶어, 같은 경우가 나오면 연산에서 배제하는 것이다.

코드

def dfs(depth):
    global ans

    if depth == M:
        ans = max(ans, int(''.join(arr)))
        return

    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            arr[i], arr[j] = arr[j], arr[i]

            check = int(''.join(arr))
            if (depth, check) not in visited:
                visited.append((depth, check))
                dfs(depth + 1)

            arr[i], arr[j] = arr[j], arr[i]


result = []
T = int(input())
for case in range(1, T + 1):
    N, M = map(int, input().split())
    arr = list(str(N))
    visited = []
    ans = 0
    dfs(0)

    result.append(f"#{case} {ans}")
for _ in result:
    print(_)