BOJ 25958 예쁜수

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

문제

$1$보다 크거나 같은 정수 $N$의 각 자리의 합을 $S$라고 할 때, $S$가 $N$의 약수라면 그 수를 예쁜수라고 하자.

지수는 자연수 $M(M \leq 5,000)$을 예쁜수들의 합으로만 표현하고 싶다.

이때 합이 $M$인 예쁜수들의 구성이 다른 경우에만 다른 방법이다.

예를 들어 $M=4$인 경우, $1+1+2=4$과 $2+1+1=4$는 같은 경우다.

지수를 도와 자연수 $M$을 예쁜수들의 합으로만 표현하는 경우의 수를 구해주자.

경우의 수는 매우 클 수 있으므로 자연수 $M$을 예쁜수들의 합으로 표현하는 경우의 수를 $K(10^6 \leq K \leq 10^7,K$는 소수$)$로 나눈 나머지를 구해주자.

---

입력

첫 번째 줄에 자연수 $M(1 \leq M \leq 5,000)$과 $K(10^6 \leq K \leq 10^7, K$는 소수$)$가 공백으로 구분되어 주어진다.

---

출력

$M$을 예쁜수들의 합으로만 표현하는 방법의 수를 $K$로 나눈 나머지를 출력하시오.

---

예제 입력 1

10 1299721

예제 출력 1

42

예제 입력 2

100 1299721

예제 출력 2

1024698

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
        int[] prettyNums = new int[M + 1];
        prettyNums[0] = 1;

        for (int i = 1; i <= M; i++) {
            int calNum = 0;
            for (int j = i; j != 0; j /= 10) {
                calNum += j % 10;
            }
            if (i % calNum == 0) {
                for (int j = i; j < prettyNums.length; j++) {
                    prettyNums[j] = (prettyNums[j] + prettyNums[j - i]) % K;
                }
            }
        }

        System.out.println(prettyNums[M]);
    }
}