[BOJ 16203 // C++] 까다로운 수 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16203번 문제인 까다로운 수 찾기이다.
문제는 아래 링크를 확인하자.

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

 

0~9의 각 숫자로 시작하는 x(2 이상)자리 A-까다로운 수의 개수는 x-1자리 A-까다로운 수에서의 정보를 이용해 계산이 가능하다. 또한, A가 9가 아니라면 x자리 A-까다로운 수의 개수는 지수적으로 증가함을 관찰할 수 있다. 이를 이용하면 A가 9가 아닌 경우 간단한 사전순 dp와 그 역추적을 이용해 문제를 해결할 수 있다.

 

한편, A가 9라면 한자리 수를 제외한 경우 9로 시작해 9와 0이 번갈아 등장하는 형태의 수만이 정답이 됨을 알 수 있다. 해당 수들을 9부터 크기순으로 살피면 원하는 수는 "10배 후 0을 더하기"와 "10배 후 9를 더하기"를 번갈아가면서 반복하는 것으로 얻을 수 있음을 알 수 있다. 즉, 9 이상의 9-까다로운 수 중 위와 같은 반복을 짝수번 해야 한다면 이는 9에 "100배 후 9를 더하기"를 적절한 횟수 반복하는 것으로 답을 구할 수 있고, 홀수번 해야한다면 이는 90에 "100배 후 90을 더하기"를 적절한 횟수 반복하는 것으로 답을 구할 수 있음을 알 수 있다.

 

일차함수에 값을 $k$회 반복해 대입하는 것은 함수의 합성을 이용하여(binary exponentiation과 같은 방법으로) $O(\lg k)$에 해낼 수 있다. 이를 이용해 A=9인 경우의 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

ll N, K;
ll A[10][10], tmp[10]; vector<ll> vec[10]; // vec[i]: i로 시작하는 수 최대 개수. 0으로 시작하는 수는 계수할 때 따로 무시
int V[10];

ll rsum(int L, int R) {
	ll ret = 0;
	for (int i = L; i <= R; i++) ret += vec[i].back();
	return ret;
}

void solve9() {
	if (N < 9) {
		cout << N << '\n';
		return;
	}
	N -= 8;

	ll ans, AA, BB;
	if (N & 1) {
		ans = 9;
		AA = 100, BB = 9;
	}
	else ans = 0, AA = 100, BB = 90;
	N /= 2;
	while (N) {
		if (N & 1) {
			ans = (AA * ans + BB) % 1000000007;
		}
		ll AAA = (AA * AA) % 1000000007, BBB = (AA * BB + BB) % 1000000007;
		AA = AAA, BB = BBB;
		N >>= 1;
	}
	cout << ans << '\n';
}

void solve() {
	cin >> N >> K;
	if (K == 9) {
		solve9();
		return;
	}
	for (int r = 0; r < 10; r++) {
		for (int c = 0; c < 10; c++) {
			if (abs(r - c) < K) A[r][c] = 0;
			else A[r][c] = 1;
		}
	}
	for (int r = 0; r < 10; r++) vec[r].clear(), vec[r].emplace_back(1);
	while (rsum(1, 9) < N) {
		N -= rsum(1, 9);
		for (int r = 0; r < 10; r++) {
			tmp[r] = 0;
			for (int c = 0; c < 10; c++) tmp[r] += A[r][c] * vec[c].back();
		}
		for (int r = 0; r < 10; r++) vec[r].emplace_back(tmp[r]);
	}
	ll ans = 0;
	memset(V, 0, sizeof(V));
	for (int i = 1; i < 10; i++) V[i] = 1;
	while (!vec[0].empty()) {
		int id = 0;
		while (1) {
			if (!V[id]) id++;
			else if (vec[id].back() >= N) break;
			else {
				N -= vec[id].back();
				id++;
			}
		}
		ans = (ans * 10 + id) % 1000000007;
		for (int i = 0; i < 10; i++) vec[i].pop_back();
		for (int i = 0; i < 10; i++) {
			if (abs(i - id) < K) V[i] = 0;
			else V[i] = 1;
		}
	}
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}

 

#랜덤 마라톤 · 코스 7 H번