백준 24268 "2022는 무엇이 특별할까" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• N보다 크면서 d진법으로 변환했을 때 각 자리 숫자가 한 번씩만 등장하는 가장 작은 수를 찾아 10진법으로 출력.
• 만약 존재하지 않으면 -1 출력

---

🛠 풀이 및 알고리즘

가능한 최댓값 계산

• d진법에서 가장 큰 d자리 숫자(d-1부터 0까지)를 구함.
• N이 이 값보다 크면 -1 출력.

1. 백트래킹(DFS)으로 순열 생성
   • d자리 숫자를 만들어야 하므로 d자리 순열을 생성.
   • visited[]를 활용해 중복 숫자 방지.
2. 숫자 크기 비교 및 변환
   • 생성된 숫자가 N보다 크면 10진법으로 변환하여 출력.
   • 가장 작은 값을 찾으면 즉시 System.exit(0);으로 프로그램 종료.

---

💡 코드

public class Baekjoon_24268 {
    static int n, d;
    static int[] visited;
    static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        d = sc.nextInt();
        visited = new int[d];
        nums = new int[d];

        // 1. d진법에서 만들 수 있는 최대값 구하기 (d-1 ~ 0)
        String maxStr = "";
        for (int i = d - 1; i >= 0; i--) {
            maxStr += i;
        }
        int max = Integer.parseInt(maxStr, d);

        // 2. n이 이미 최댓값 이상이면 -1 출력
        if (n >= max) {
            System.out.println(-1);
            return;
        }

        // 3. 백트래킹 탐색 시작
        dfs(0);
    }

    static void dfs(int L) {

        // 첫번째 자리가 0이면 안됨
        if (L == d && nums[0] != 0) {
            // 4. 숫자 조합을 문자열로 변환
            String res = "";
            for (int x : nums) {
                res += x;
            }
            if (n < Integer.parseInt(res)) {
                System.out.println(Integer.parseInt(res, d));
                System.exit(0);
            }
            return;
        }
        // 5. 숫자 순열 생성
        for (int i = 0; i < d; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                nums[L] = i;
                dfs(L + 1);
                visited[i] = 0;
            }
        }
    }
}

---

🏆 시간 복잡도 분석

• 백트래킹 탐색 (O(d!))
  • d자리 순열을 생성하므로 최대 O(d!).
  • d ≤ 10이므로, 10! = 3,628,800 정도로 충분히 탐색 가능.