BOJ 3026 V

* BOJ 3026 V

[분류 : 다이나믹/ 가지치기]

  [풀이]

  컷팅이 중요한 문제.

  1. X가 10^5보다 크거나 같은 경우

  A=1, B=10^11인 최악의 경우에서 X의 배수를 구할 때 10^6의 연산수가 필요해요. 이 경우엔 충분히 브루트포스로 계산이 가능합니다.

  2. X가 10^5보다 작은 경우

  최악의 경우를 생각해봅시다. X = 1, A = 1, B = 10^11이라면 브루트포스로 최대 10^11번을 계산해야하기 때문에 시간초과가 날 것임이 자명합니다.

    

  [다이나믹]

  자리수로 생각해봅시다. 수가 최대 10^11이므로 12자리가 자리수 최대가 됩니다.

  관찰포인트는 인접한 자리수 간의 관계입니다. X=151이고 현재 10^3의 자리수를 구해야한다고 해봅시다. 이 때 1의 자리, 10의 자리 그리고 10^2자리에 어떤 숫자가 존재했을지 모르겠으나 X로 나눈 나머지가 76이라고 해봅시다. 그러면 현재 10^3의 자리수에 어떤 숫자를 넣느냐에 따라 이 나머지 값이 고정됩니다.

10^3에 넣을 숫자	10^3까지 숫자를 정한 수를 X로 나눈 나머지
0	(0 * 1000 + 76)%X = 76
1	(1 * 1000 + 76)%X = 19
2	(2 * 1000 + 76)%X = 113
3	(3 * 1000 + 76)%X = 56
4	(4 * 1000 + 76)%X = 150
5	(5 * 1000 + 76)%X = 93
6	(6 * 1000 + 76)%X = 36
7	(7 * 1000 + 76)%X = 130
8	(8 * 1000 + 76)%X = 73
9	(9 * 1000 + 76)%X = 16

 이렇게 이전에 어떤 나머지를 가지고 있었는지를 가지고 현재 자리수에 어떤 수를 넣을 것인지 정하여 나머지 계산이 가능합니다. 따라서 함수의 프로토타입을 아래처럼 정의해봅시다.

: A보다 작은 수 중에 position 자리수를 가지는 수 중에서 나머지가 remain인 것의 개수

: A보다 작은 수 중에 position 자리수인 수 중에서 나머지가 remain인 것의 개수

  여기서 데이터가 부족합니다. 함수에 A보다 작아야함을 나타낼 수 있는 의미를 가지는 인자가 필요합니다. 이 인자에 따라 현재 자리수에서 고를 수 있는 수는 제한될겁니다. -> limit 변수

  또한 입력 데이터에서 0을 사용할 수 없더라도 position에서 0을 사용할 수 있는 경우가 있습니다. 그건 바로 A보다 낮은 자리수를 갖는 수인 경우에 해당합니다. 가령 A=4231이라면 A보다 아래 있는 수 중 하나는 333으로 가져올 수 있습니다. 이는 10^3의 자리수에 0을 넣은 것이라고 볼 수 있습니다. 따라서 앞에서 수를 구성했는지 안했는지를 나타내는 플래그가 필요합니다 -> used 변수

  아래처럼 프로토타입을 완성할 수 있습니다.

: A보다 작은 수 중에 position 자리수인 수 중에서 나머지가 remain인 것의 개수. 단 현재 position 자리수에서 사용할 수 있는 건 limit, used에 따라 달라질 수 있다.

  이 구조는 현재 내가 remain이란 나머지가 필요한데, 현재 position에서 k를 선택하면 k * 10^position을 덧셈하는 꼴이니 다음 재귀에선 (remain - k * 10^position + X) % X이란 나머지를 필요로 한다는 구조입니다. 결국 똑같은 문제를 계속 풀어야하니 다이나믹 프로그래밍인 것이죠.

#include<cstdio>
#include<cstring>
using ll = long long;
const ll BRANCH = 1e5;
ll X, dp[2][2][13][BRANCH], p10[12] = { 1 };
int N, can[10];
void gv(ll A, int* a) {
	int i, t;
	N = 0;
	while (A) {
		a[N++] = A % 10;
		A /= 10;
	}
}
ll rec(int l, int u, int p, int r, int* a) {
	if (p == -1) return !r;
	ll& ret = dp[l][u][p][r];
	if (ret != -1) return ret;
	ret = 0;
	int i, L = l ? a[p] : 9;
	for (i = 0; i <= L; i++) if (can[i] || (!i && !u && p))
		ret += rec(l && i == L, u || i > 0, p - 1, (r - p10[p] * i % X + X) % X, a);
	return ret;
}
int main() {
	char c[11];
	ll A, B, ans = 0, t, v, f;
	int i, a[12], b[12];
	for (i = 1; i < 12; i++) p10[i] = 10 * p10[i - 1];
	scanf("%lld%lld%lld\n%s", &X, &A, &B, &c);
	for (i = 0; c[i]; i++)
		can[c[i] - '0'] = 1;
	if (X < BRANCH) {
		memset(dp, -1, sizeof dp);
		gv(B, b);
		ans = rec(1, 0, N - 1, 0, b);
		memset(dp, -1, sizeof dp);
		A--;
		gv(A, a);
		ans -= rec(1, 0, N - 1, 0, a);
	}
	else {
		t = X;
		while (t <= B) {
			v = t;
			f = 1;
			while (v) {
				f &= can[v % 10];
				v /= 10;
			}
			ans += f && A <= t;
			t += X;
		}
	}
	printf("%lld", ans);
	return 0;
}