[백준 24268] 2022는 무엇이 특별할까? (C#, C++) - soo:bak

문제 링크

24268번 - 2022는 무엇이 특별할까?

설명

정수 N과 진법 d (2 ≤ d ≤ 9)가 주어지는 상황에서, d진법으로 표현했을 때 0부터 d-1까지의 숫자를 정확히 한 번씩 사용하는 수 중 N보다 큰 가장 작은 수를 구하는 문제입니다.

맨 앞자리는 0이 될 수 없으며, 조건을 만족하는 수가 없으면 -1을 출력합니다.

접근법

d진법에서 0부터 d-1까지 d개의 숫자를 정확히 한 번씩 사용하므로, d자리 수의 각 자리는 이 숫자들의 순열입니다.

d가 최대 9이므로 가능한 순열의 개수는 최대 9! = 362,880개로 모든 경우를 확인할 수 있습니다.

0부터 d-1까지의 숫자 배열을 만들고 모든 순열을 생성합니다.

각 순열마다 맨 앞자리가 0인지 확인하고, 0이면 건너뜁니다.

맨 앞자리가 0이 아닌 순열에 대해 d진법 값을 10진법으로 변환합니다.

d진법을 10진법으로 변환하는 방법은 왼쪽부터 각 자릿수를 순회하며 결과 = 결과 × d + 현재자릿수 식으로 계산하는 것입니다.

예를 들어 3진법 “120”을 10진법으로 변환하면:

• 0 × 3 + 1 = 1
• 1 × 3 + 2 = 5
• 5 × 3 + 0 = 15

변환된 값이 N보다 크면서 지금까지 찾은 값보다 작으면 갱신합니다.

모든 순열을 확인한 후 갱신된 값이 있으면 출력하고, 없으면 -1을 출력합니다.

예를 들어 N = 2022, d = 4일 때:

• 가능한 순열: 0123, 0132, …, 3210 (4! = 24개)
• 맨 앞이 0인 경우 제외: 1023, 1032, …, 3210
• 각 순열을 4진법으로 해석: 1023₄ = 1×64 + 0×16 + 2×4 + 3 = 75, …
• N(2022)보다 큰 값 중 최소값을 찾음

---

Code

C#

using System;

namespace Solution {
  class Program {
    static bool NextPermutation(int[] a) {
      var i = a.Length - 2;
      while (i >= 0 && a[i] >= a[i + 1]) i--;
      if (i < 0) return false;

      var j = a.Length - 1;
      while (a[j] <= a[i]) j--;
      (a[i], a[j]) = (a[j], a[i]);
      Array.Reverse(a, i + 1, a.Length - (i + 1));

      return true;
    }

    static void Main(string[] args) {
      var parts = Console.ReadLine()!.Split();
      var n = long.Parse(parts[0]);
      var d = int.Parse(parts[1]);

      var digits = new int[d];
      for (var i = 0; i < d; i++)
        digits[i] = i;

      var ans = -1L;

      while (true) {
        if (digits[0] != 0) {
          var val = 0L;
          for (var i = 0; i < d; i++)
            val = val * d + digits[i];
          if (val > n && (ans == -1 || val < ans))
            ans = val;
        }
        if (!NextPermutation(digits)) break;
      }

      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n; int d; cin >> n >> d;

  vi digits(d);
  iota(digits.begin(), digits.end(), 0);

  ll ans = -1;

  while (true) {
    if (digits[0] != 0) {
      ll val = 0;
      for (int x : digits)
        val = val * d + x;
      if (val > n && (ans == -1 || val < ans))
        ans = val;
    }
    if (!next_permutation(digits.begin(), digits.end())) break;
  }

  cout << ans << "\n";

  return 0;
}