1039. 교환

1039번: 교환

---

숫자의 배치 순서를 바꿔서 수를 최대로 만들어야 하는 문제이다.

 

무식하게 풀어보기

모든 가능한 $(i, j)$ 쌍을 바꿔 보는 방법을 생각해 볼 수 있다, 그러나 경우의 수가 최대 $\left(\begin{array}{c}7\\ 2\end{array}\right)^{10}=16,679,880,978,201$개나 있으므로 완전 탐색으로는 문제를 풀 수 없다.

 

그렇다면 기억해 보자

메모이제이션을 활용하여 중복 계산을 줄여 보자. 다음을 정의한다.

 

$ans(n, dep) = dep$번 교환하여 얻은 수가 $n$일 때, 교환을 완료하여 얻을 수 있는 최대의 수

 

교환 가능한 모든 쌍에 대하여 나머지 횟수만큼 교환한 결과를 모두 탐색하고, 최댓값을 저장한다. 이때 이전에 탐색한 결과가 있다면 중복 계산하지 않아야 한다.

 

$ans(n, dep) = \max(exchanged, n+1) $ $for$ $all$ $available$ $exchanged$

 

주의

다음의 교환이 가능하다.

100 → 100

---

풀고 나서 solved.ac 태그를 보고 조금 놀랐다. 이걸 어떻게 BFS로 풀지?