✅ 백트래킹

문제

링크

풀이

1. 문제 접근

처음 문제를 읽고 이게 무슨 소리여..ㅎㅎ..

차근차근 문제를 분해해보자.

• 1 ≤ i < j ≤ M인 i와 j를 골라 i번 위치의 숫자와 j번 위치의 숫자를 바꾼다.
  -> 만들 수 있는 가장 큰 수를 구해야 하므로 i위치의 숫자가 j위치의 숫자보다 작을 경우에만 바꿀 수 있다.
• 이때, 바꾼 수가 0으로 시작하면 안 된다.
  -> i 가 1일 때, j 가 0 이면 안된다.
• 만약 연산을 K번 할 수 없으면 -1을 출력

2. 문제 해결 로직 (풀이법)

두 위치의 숫자를 바꿔가며 최종값이 최대가 되야 한다.
즉, 두 위치를 바꿨을 때 값이 그동안의 값보다 크다면 바꿔주고 아니라면 바꾸지 않는다.
-> 최대 값을 저장해가면서 바꿔야 함

두 위치를 바꿨을 때 이전에 나왔던 수가 나오면 안된다. (또 나오면 무한 루프임;)
N은 최대 1,000,000이기 때문에 나온 모든 수들을 저장하면서 나왔는지 안나왔는지 판별할 수는 없고
중복된 수가 나왔을 때 가지치기를 해줘야 한다. -> 백트래킹 (Backtracking)

의사코드

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분