[백준] 24268번. 2022는 무엇이 특별할까?(JAVA)

문제

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

---

풀이(32분)

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

public class Main {

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

        long N = Long.parseLong(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        List<Long> v = new ArrayList<>();
        long[] fact = new long[d];
        fact[0] = 1;
        for (int i = 1; i < d; i++) {
            fact[i] = fact[i - 1] * d;
        }

        for (int i = 0; i < d; i++) {
            v.add((long) i);
        }

        boolean flag = true;
        long ans = -1;

        while (flag) {
            if (v.get(0) != 0) {
                long tmp = 0;
                for (int i = 0; i < d; i++) {
                    tmp += v.get(i) * fact[d - 1 - i];
                }
                if (tmp > N) {
                    ans = tmp;
                    break;
                }
            }
            flag = nextPermutation(v);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(ans);
        System.out.println(sb.toString());
    }

    static boolean nextPermutation(List<Long> v) {
        int i = v.size() - 2;
        while (i >= 0 && v.get(i) >= v.get(i + 1)) i--;
        if (i < 0) return false;
        int j = v.size() - 1;
        while (v.get(i) >= v.get(j)) j--;
        Collections.swap(v, i, j);
        Collections.reverse(v.subList(i + 1, v.size()));
        return true;
    }
}

---

문제 풀이 전략

 

처음엔 dfs로 진행하려고 했지만 d가 9진법까지로 한정되어 있기 때문에 순열을 통해 모든 경우를 브루트포스 하여 문제를 해결했다!