[swea] 1244번: 최대상금 - 파이썬(python)

완전탐색을 이용한 풀이.

갈피를 잡지 못해 다른 분들의 코드를 참고했다.

 

0번째 인덱스부터 탐색을 시작하는데, 현재인덱스값 이상인 값이 있다면, 현재 인덱스의 값과 교환한다.

그런다음,(현재 탐색중인 인덱스 (i) , 교환횟수+1) 을 dfs 인자로 주고 탐색한다.

만약 교환횟수를 모두 써버렸다면, 최댓값보다 현재 교환된 숫자결과가 더 크다면 갱신한다.

만약, 이미 내림차순 정렬이 되어있어 교환횟수가 남아있는 상태라면,

홀수라면 마지막 1,2번째 인덱스를 바꾸고, 짝수라면 그대로 둔다.

 

 

나의 풀이

def dfs(idx, n):
    global max_val
    if n == int(cnt):
        max_val = max(max_val, int(''.join(data)))
        return
    for i in range(idx, N):
        for j in range(i + 1, N):
            if data[i] <= data[j]:
                data[i], data[j] = data[j], data[i]
                dfs(i, n + 1)
                data[i], data[j] = data[j], data[i]
    if not max_val and n<int(cnt) : # 이미 내림차순 정렬이되었는데 교환횟수가 남았다면
        if (int(cnt)-n) % 2 : # 남은 교환횟수가 홀수라면
            data[-1],data[-2] = data[-2],data[-1]
        dfs(idx,int(cnt))


T = int(input())
answer = []

for t in range(1, T + 1):
    data, cnt = input().split()
    data = list(data)
    N = len(data)
    max_val = 0
    dfs(0, 0)
    answer.append(f'#{t} {max_val}')
print(*answer, sep='\n')