BOJ - 줄어드는 숫자

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

1174번: 줄어드는 숫자

 

• 백트래킹 탐색 문제이다.
• 총 1023가지 경우의 수가 나온다. 첫 번째가 1부터 시작함에 주의한다.
• 다음 탐색 조건을 앞의 숫자와 비교하여 작을 시 탐색한 뒤 주어진 번째 수가 맞다면 탈출 하는 방법을 사용했다.

 

import java.io.*;
import java.util.*;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N = 0;

    //선택 할 수 있는 십진법 가지수
    private static String choices = "0123456789";
    private static int dpOrder = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        //최대 N자리를 선택 하는 DP
        for (int i = 1; i <= 10; i++) {
            boolean[] visit = new boolean[11];
            dp(visit, 0, "", i);
        }

        //찾을 수 없다면 -1 출력
        System.out.println(-1);
    }

    private static void dp(boolean[] visit, int depth, String number, int numberOfDigit) {
        if (depth == numberOfDigit) {
            if (N == dpOrder + 1) {
                //가지수 안에 있을 시 바로 종료
                System.out.println(number);
                System.exit(0);
            }

            dpOrder += 1;
            return;
        }

        for (int i = 0; i < choices.length(); i++) {
            if (visit[i]) continue;
            visit[i] = true;

            if (depth == 0) {
                dp(visit, depth + 1,
                        number + choices.charAt(i),
                        numberOfDigit);
            } else {
                
                //앞 자리수 보다 작은 경우에만 탐색함
                int front = Character.getNumericValue(number.charAt(number.length() - 1));
                int next = Character.getNumericValue(choices.charAt(i));
                if (front > next) {
                    dp(visit, depth + 1,
                            number + choices.charAt(i),
                            numberOfDigit);
                }
            }

            visit[i] = false;
        }
    }
}