[SWEA] 최대 상금

[SWEA] 최대 상금

Problem URL : 최대 상금

import sys
sys.stdin = open("input.txt", "r")


T = int(input())


def dfs(idx, end, cnt):
    global ans, repeated
    if cnt == 0:
        n = int("".join(N))
        if ans < n:
            ans = n
        return
    if idx == end:
        if not repeated and cnt % 2 == 1:  # 전체 자리수를 다 순회했음에도 교환 횟수가 남았고
            N[-2], N[-1] = N[-1], N[-2]    # 중복되는 수가 없고, 남은 교환횟수가 홀수일 때
        n = int("".join(N))                # 어쩔 수 없이 마지막 2개의 수를 교환
        if ans < n:
            ans = n
        return
    max_num = "-1"
    max_list = []
    for i in range(idx, end):
        if max_num < N[i]:
            max_num = N[i]
            max_list = [i]
        elif max_num == N[i]:
            max_list.append(i)  # 최댓값이 현재 idx위치의 숫자카드랑 교환될 후보들이다.
    for i in max_list:
        if i == idx:
            dfs(idx + 1, end, cnt)
            continue
        N[idx], N[i] = N[i], N[idx]
        dfs(idx + 1, end, cnt - 1)
        N[idx], N[i] = N[i], N[idx]  # 백트래킹


for tc in range(1, T + 1):
    N, E = input().split()
    N, E, L = list(N), int(E), len(N)
    ans = 0
    repeated = False
    numbers = [0] * 10
    for i in N:
        numbers[int(i)] += 1
    for i in range(10):
        if numbers[i] > 1:  # 중복 체크
            repeated = True
            break

    dfs(0, L, E)
    print("#{} {}".format(tc, ans))

Comments

자잘한 실수를 해서 생각보다 시간이 좀 걸렸다.
매턴 교환해야할 후보들이 최댓값인 숫자 카드들 전부인 것을 주의해야 한다.