[1039] 교환

문제

https://www.acmicpc.net/problem/1039

풀이

일단 연산을 할 수 없는 경우를 걸러준다.

연산을 할 수 없는 경우는 두 가지가 있다. 자릿수가 하나 밖에 없어서 교환 가능한 숫자가 없는 경우와 두 자리 수지만 일의 자리 수가 0이라 교환을 할 수 없을 경우가 있다. 이 두 가지에 해당할 경우 -1를 출력하고 종료한다.

가장 큰 값을 만들기 위해 큰 자릿수부터 내림차순으로 교환을 해줄 것이다. 해당 자릿수보다 작은 자릿수의 숫자들 중 가장 큰 값과 교환한다.

이 때 생각해야할 것이 두 가지가 있다. 큰 값을 만들었지만 남은 연산의 횟수 남아있는 경우이다. 이럴 경우는 간단히 생각해서 값에 크게 영향을 주지않는 자리 수의 교환으로 횟수를 써버리면 된다. 일의 자릿수와 십의 자릿수를 남은 횟수만큼 교환해주면 되는데 여기서 알 수 있는 것은 실제로 연산을 하지 않아도 남은 횟수가 짝수라면 지금의 숫자와 동일해질 것이고, 홀수라면 한 번의 교환만 해주면 된다는 것을 알 수 있다.

다음으로 생각해야하는 것은 해당 자릿수보다 작은 자릿수에서 가장 큰 값을 가진 자릿수가 한 개 이상일 수도 있다는 점이다. 예를들어 N = 3661, K = 1 와 같은 경우 첫 번째 자릿수를 교환할 때 두 번째 자릿수와 교환하게 된다면 6361이므로 6631을 만들 수 있음에도 불구하고 이런 경우를 놓칠 수 있게된다. 따라서 가장 큰 값을 가진 자리 수가 여러 개일 경우 dfs로 모든 교환의 경우를 탐색해주었다.

내 코드

import sys

N, K = sys.stdin.readline().split()
if len(N) == 1 or (len(N) == 2 and N.count('0') == 1):
    print(-1)
    exit()
K = int(K)
nums = [int(n) for n in N]
result = 0

def dfs(index, change):
    global result, K
    if (K - change) == 0 or index == len(nums) - 1: # 연산
        if (K - change) % 2 == 0:
            result = max(result, int(''.join(map(str, nums))))
        else:
            nums[-1], nums[-2] = nums[-2], nums[-1]
            result = max(result, int(''.join(map(str, nums))))
            nums[-1], nums[-2] = nums[-2], nums[-1]
        return
    max_index = [index]
    for i in range(index + 1, len(nums)):
        if nums[max_index[0]] <= nums[i]:
            if nums[max_index[0]] == nums[i]:
                max_index.append(i)
            else:
                max_index = [i]
    for i in max_index:
        nums[index], nums[i] = nums[i], nums[index]
        n_change = change + 1 if i != index else change
        dfs(index + 1, n_change)
        nums[index], nums[i] = nums[i], nums[index]
dfs(0, 0)
print(result)