[백준] 24268번 2022는 무엇이 특별할까? - C/C++

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

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

백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다.

그렇다. 2022를 5진법으로 표현하면 31042(5)로, 5진법의 각 숫자인 0, 1, 2, 3, 4가 모두 한 번씩 나타난다. 다음에 이런 년도가 오려면 2054년이 되어야 한다.

수 N과 진법 d가 주어진다. 당신은 수 N보다 크면서, d진법으로 표현했을 때 d진법의 숫자가 모두 정확히 한 번씩 등장하는 가장 작은 수를 찾아야 한다. 단, 수를 표기할 때는 앞에 불필요한 0이 존재해서는 안 된다.

입력

첫 번째 줄에 수 N과 진법 d가 공백을 사이에 두고 10진법으로 주어진다.

출력

첫 번째 줄에 N보다 크면서 d진법으로 표현했을 때 d진법의 숫자가 모두 정확히 한 번씩 등장하는 수 중 가장 작은 것을 10진법으로 출력한다.

만약 그런 수가 존재하지 않는다면, 첫 번째 줄에 −1을 대신 출력한다.

---

직접 하나하나 확인해보아야 하는 브루트포스 알고리즘의 문제이다. 하지만 조금 더 편리하게 확인하는 코드를 구사하는 것이 관건이다! 우선 N을 받으면 조건에 만족하는 답의 최댓값은 d-1 d-2 d-3 .... 0 이므로 만약 N 이 이 값보다 크거나 같다면 -1을 출력해야한다. 그렇지 않다면 값을 구해야한다. 우선 N의 d진수 표현을 배열 arr 에 저장한다. 그 다음 반복문을 돌면서 1을 더해주면서 d진수 표현을 조정해준다. 그 다음 이 값의 숫자들을 확인하는데 이때 변수 vis 로 비트마스킹 기법을 사용하여 나온 숫자들을 기록한다. 예를 들어 4 가 나왔으면 (1 << 4) 즉 (10000)으로 나타내어 만약 모든 숫자가 겹치는 경우 없이 모두 1 이 되었다면 그 숫자를 반환하면 된다. 이때 첫 숫자는 0이 나올 수 없으므로 arr[d-1]이 0 인 값으로 vis 가 ((1<<d) -1))이 되었다면 아쉽지만 답이 아니다.

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int N=0, d;
int arr[101] = { 0 };
int max_num = 0;


int solve(int n) {
	int vis = 0;
	for (int i = 0; i < d; i++) {
		arr[i] = n % d;
		n = n / d;
	}	
	while (n <= max_num) {
		vis = 0;
		arr[0] += 1; N++;
		for (int i = 0; i < d; i++) {
			if (arr[i] == d) {
				arr[i + 1]++; arr[i] = 0;
				break;
			}
		}
		for (int i = 0; i < d; i++) {
			if (!(vis & (1 << arr[i]))) {
				vis = vis | (1 << arr[i]);
				if (vis == (1 << d) - 1 && arr[d-1] != 0)
					return N;
			}
			else break;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> N >> d;

	
	for (int i = 0; i < d; i++) {
		max_num += i * pow(d, i);
	}
	if (N >= max_num) {
		cout << -1 << "\n";
	}
	else {
		cout << solve(N);
	}

	return 0;
}

---

문제가 보기보다 신경써야 할 조건이 많은 문제였다. 놓친 부분이 여러가지가 있었는데 숫자가 정확히 한번씩 나오는 경우, 첫 숫자가 0이 아닌 경우 , 보다 큰 경우의 조건을 신경 쓰지 못하고 여러번 제출을 했다가 틀렸다. 이 모든 것을 고쳤을 때 100퍼센트에서 시간초과가 떴다. 기존의 코드는 매번 N 의 d 진수 숫자를 나눗셈을 통해서 구했다 하지만 이렇게 되니 숫자가 1 차이나면 d진수 숫자를 쉽게 구할 수 있는데도 매번 나눗셈을 여러번 진행하여 시간이 오래걸리게 된다. 그래서 한번의 나눗셈을 통해 arr 배열을 구해놓고 올림을 구현하여 N이 증가하여도 나눗셈을 여러번 할 필요가 없도록 하였더니 통과를 하였다.

이번 문제는 첫 갈피는 맞게 잡아서 비트마스킹까지 사용한 것은 좋았는데 문제를 너무 쉽게 생각하고 문제를 대충 읽은 것 같다. 이 말을 적으면서 데자뷰처럼 이전 포스팅에서 여러번 적은 것 같은 기억이 난다. 특히 쉬워보이는 문제만 보면 코드를 무턱대고 짜는 습관이 무서운것 같다.