난이도

Gold 3

인증

문제

준혁이는 $0$부터 $9$까지의 숫자 중에서 서로 다른 숫자를 $N$개 골랐다. 준혁이가 고른 숫자만으로 이루어진 $M$자리의 양의 정수 중에서 $K$의 배수는 몇 개인지 구해보자. 단, $M$자리의 양의 정수는 숫자 $0$으로 시작할 수 없으며, 조건을 만족하는 양의 정수가 매우 많을 수 있기 때문에 그 개수를 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 구한다. 이 수는 소수이다.

입력

첫째 줄에 정수 $N,M,K(1\le N\le 10;1\le M\le 100;2\le K\le 1\, 000)$이 공백으로 구분되어 주어진다.

둘째 줄에 준혁이가 고른 숫자 $a_1,a_2,\cdots ,a_N(0\le a_i\le 9)$이 공백으로 구분되어 오름차순으로 주어진다.

출력

준혁이가 고른 숫자만으로 이루어진 $M$자리의 양의 정수 중에서 $K$의 배수의 개수를 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.

예제 입력

10 1 2
0 1 2 3 4 5 6 7 8 9

예제 출력

4

해설 및 후기

간단하게 생각하고 풀려고 했지만, 마냥 간단한 문제가 아니었다. 첫 번째 접근은 M자리에 대해서 K의 배수가 몇개 있는지 구하는 방식이었다. 결과론적으로 이차원 DP를 사용하는 것은 맞았지만, M이 최대 100이나 되므로 각 배수를 순회하는 것은 굉장히 많은 자원이 필요하다.

먼저 M자리 숫자를 만들려고 할 때, Bottom-Up방식의 풀이를 이용할 것이므로 각 순회에 따라 한 자리씩 M까지 붙여나갈 것이다. 이때 새롭게 만들어지는 수는, (이전 숫자 * 10 + 뒤에 붙이는 숫자) 라고 할 수 있다. 그리고 만들어진 이 숫자가 k로 나누어떨어지는지 궁금하다.

여기서 ‘나누어 떨어지는’이란, MOD의 결과가 0임을 의미하므로, (새롭게 만들어진 수)%k가 0인지를 확인하면 된다. 정답의 수가 큰 알고리즘 문제에서 자주 사용되듯이, MOD연산은 더하거나 곱한 값의 MOD값을 구하기 위해 연산 내의 값을 먼저 MOD해도 동일한 값을 구할 수 있다. 즉 (N+M)%K = (N%K+M%K)%K 그리고 (NM)%K = (N%KM%K)%K

따라서 점화식을 세울 수 있다. 이전 수에 대한 나머지 값을 알 수 있으므로, 새롭게 구한 값이 k로 나누었을 때 나머지가 몇인지 판별할 수 있기 때문이다.

DP를 활용할 리스트 l[i][j]에서, i는 문자열의 개수(i=m-1일때의 값을 구해야 한다), 그리고 j에는 그 문자열의 개수에서 k로 나눈 나머지가 j인 숫자의 갯수들이 들어간다.

즉 첫 행에 대해서는 모두 1로 설정하고, 다음 행부터 각 숫자들을 순회하며 j의 나머지를 갖는 숫자의 갯수를 추가한다.

제출 코드

n,m,k = map(int, input().split())
nums = list(map(int,input().split()))

l = [[0 for _ in range(k)] for _ in range(m)]
for u in nums:
    if(u == 0): continue
    l[0][u%k] += 1
for i in range(1, m):
    for j in range(k):
        if(l[i-1][j] == 0): continue
        for u in nums:
            l[i][(j*10+u)%k] += l[i-1][j]
            l[i][(j*10+u)%k] = l[i][(j*10+u)%k] % 1000000007

print(l[m-1][0])