[백준/1039] 교환 (Python)

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

1039번: 교환

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:10:08

 

---

 

문제 설명

 

 

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

입력 예시

 

16375 1

 

출력 예시

 

76315

 

 

---

 

풀이

 

기껏 풀고 나니 1년 전 과거의 내가 풀었다는 걸 그제야 알게 된 문제... 심지어 풀이법도 재귀를 쓰느냐 반복문을 이용하냐의 차이뿐이었다.

 

핵심은 1 ~ K번까지 주어진 연산을 수행하는 경우를 완전 탐색해 보는 것. N값의 자릿수는 최대 7이므로, 한 차례에서 두 숫자를 바꾸는 경우의 수는 7*6 = 42가지 경우가 나올 수 있으며 바꾼 수가 0으로 시작하는 경우를 제하면 더 적어진다. 또한 최대 K는 10이므로 경우의 수 자체가 최대 42^10이 되지만, 우리는 숫자의 범위 상 이 경우의 수가 겹치는 경우가 매우 많음을 알 수 있다. 동일 차례에서 한 차례 만들어냈던 숫자는 다시 방문하지 않도록 visited를 작성하여 활용하면 가지치기로 경우의 수가 더 줄어든다. 즉 그래프 탐색 문제로 풀이할 경우 쉽게 풀 수 있겠다.

 

풀이 코드

N, K = input().split()
N = list(N)
M = len(N)
K = int(K)

answer = -1
visited = [[False]*1000001 for i in range(K+1)]
def dfs(idx) :
  global answer
  if idx == K :
    answer = max(answer, int(''.join(N)))
    return
  for i in range(M-1) :
    for j in range(i+1, M) :
      if i == 0 and N[j] == '0' :
        continue
      N[i], N[j] = N[j], N[i]
      num = int(''.join(N))
      if not visited[idx][num] :
        visited[idx][num] = True
        dfs(idx + 1)
      N[i], N[j] = N[j], N[i]

dfs(0)
print(answer)

풀이 완료!