[JAVA] 백준 (골드5) 1174번 줄어드는 수

링크

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

---

입력 예제

19

---

출력 예제

42

---

풀이

줄어드는 수의 최댓값은 9876543210이다. 수가 매우 크기때문에 모든 수에 대해서 탐색할 수는 없다. 그래서 줄어드는 수를 만족하는 모든 경우의 수를 탐색하면서 가지치기를 해야 한다.

숫자 0~9를 내림차순으로 사용해가며 줄어드는 수를 만들어 간다. 우선 숫자 0부터 시작하여 자릿수를 증가시켜가며 수를 만든다. 그리고 재귀의 depth가 증가할 수록 사용하는 수의 인덱스도 증가시킨다.

- 0
  - 9
    - 98

이때 9에 다음 숫자인 8을 추가하면 98이 되는데, 이런식으로 진행한다면 만족하는 모든 경우의 수를 탐색할 수 없으므로 재귀 호출을 두가지 방식으로 한다.

• 자릿수를 증가시키며 다음 수를 추가
• 수는 그대로 유지시키며 인덱스만 증가

- 0
  - 9
    - 98
      - 987
      - 98
    - 9
      - 97
      - 9
  - 0
    - 8
      - 87
      - 8
    - 0
      - 7
      - 0

이렇게 하면 모든 경우의 수를 탐색하며 불가능한 경로에 대해서는 탐색하지 않는다. 백트래킹을 코드로 구현하면 다음과 같다.

private static void dfs(long number, int index) {
    if (!descendingNumbers.contains(number)) {
        descendingNumbers.add(number);
    }
    
    //0까지 사용했다면 재귀 종료
    if (index >= NUMBERS.length) {
        return;
    }
    
    //number의 일의 자리에 숫자 추가
    dfs(10 * number + NUMBERS[index], index + 1);
    //number 유지
    dfs(number, index + 1);
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/*
백준 / 줄어드는 수 / 골드5
https://www.acmicpc.net/problem/1174
 */
public class Main {

    private static final int[] NUMBERS = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    private static final List<Long> descendingNumbers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        dfs(0, 0);
        
        Collections.sort(descendingNumbers);  //순서를 위해 정렬
        
        if (N > descendingNumbers.size()) {
            System.out.println(-1);
        } else {
            System.out.println(descendingNumbers.get(N - 1));
        }
    }

    private static void dfs(long number, int index) {
        if (!descendingNumbers.contains(number)) {
            descendingNumbers.add(number);
        }

        //0까지 사용했다면 재귀 종료
        if (index >= NUMBERS.length) {
            return;
        }

        //number의 일의 자리에 숫자 추가
        dfs(10 * number + NUMBERS[index], index + 1);
        //number 유지
        dfs(number, index + 1);
    }
}