앳코더90 - 005 - Restricted Digits（★7）

https://atcoder.jp/contests/typical90/tasks/typical90_e

005 - Restricted Digits（★7）

난이도 부터 풀고싶지 않게 만드는 문제이다.

 

서브태스크 1번 은 할만 하다라는 평은 듣고 트라이 해 보았다.

읽어보니 박성원(P5) 문제와 매우 유사해 보였다.

 

 N B K를 입력받았을때

K개의 수열이 주어진다 (1 <= x <= 9)

 

N자리의 숫자를 만들때 해당숫자가 B로 나뉘어지는 경우의 수를 구하여라

 

이를 dp [ 사용한 k수열의 index ][ 해당 수의 나머지 ] = 경우의 수

( 나머지 * 10 + 수열 k ) % B 가 이전의 배열 값과 같다는 점화식을 이용하면 score 1점을 얻을 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const int INF = 100000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

ll N, B, K;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> B >> K;

	vector<vector<ll>> cache(N + 1, vector<ll>(B +1, 0));
	
	vector<int> v;
	
	rep(i, K)
	{
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	cache[0][0] = 1;
	rep1(i, N)
	{
		for (int j = 0; j < K; j++)
		{
			for (int k = 0; k < B; k++)
			{
				cache[i][(k * 10 + v[j]) % B] = ( cache[i][(k * 10 + v[j]) % B] + cache[i - 1][k] ) %MOD;
			}
		}
	}
	cout << cache[N][0];
   
	return 0;
}

 

나머지는 어떻게 해야되는지 해설을 읽어봐도 모르겠어서 추후에 공부해보겠다.