[자바] 백준 30025 - K의 배수 (java)

목차

문제 : boj30025

 

 

필요 알고리즘

• DP (동적 계획법), 수학
  
  • DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게 할까?

 

  M자리 수를 한방에 만들 생각을 하지 않고, 1자리수 부터 M자리 수를 차례대로 만드는걸 생각해보자. 이 경우 자릿수를 늘리는 과정은 매번 '이전 숫자x10+a' 를 하는 과정이다. a는 주어진 N개의 숫자이다. 이 때 우리가 알아야 하는건 K의 배수가 몇 개인지 이고, K의 배수라는 말은 'K로 나눈 나머지가 0이다' 라는 말과 동일한 말이다. 그리고 나머지 연산엔 다음과 같은 식이 성립한다.

 

  즉, 최종적으로 K로 나누어 떨어지는지 알기 위해서는 실제 수가 필요한게 아니라 그냥 이전 숫자를 K로 나눈 나머지만 알면 된다는 얘기이다. 그리고 K로 나눈 나머지는 [0, K-1] 의 범위를 가진다. 그러므로 다음과 같이 동적 계획법을 짜볼 수 있다.

dp[x][y] = x+1 자리수로 만들 수 있는 수 중 K로 나눈 나머지가 y인 경우의 수

 

  그럼 dp[x][(이전 수*10+a)%K] += dp[x-1][이전 수] 와 같이 x-1값의 dp 배열을 가지고 현재 x값의 dp배열 값을 정할 수 있게 된다. O(NMK)로 답을 구할 수 있고, 실제로 보는 O(N^M)에 비해 엄청나게 빠르게 답을 구할 수 있게 된다. 그리고 답은 10^9+7로 나눈 나머지를 구한다고 되어있고, 위에서 설명한 것과 마찬가지로 그냥 매번 10^9+7로 나눈 나머지만 유지해도 답을 구하는데 문제 없다.

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] num = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[m][k];
        for (int cur : num) {
            if (cur == 0) continue;
            dp[0][cur%k] += 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < k; j++) {
                int bf = dp[i-1][j];
                if (bf == 0) continue;

                for (int cur : num) {
                    int nextNum = j*10+cur;
                    nextNum %= k;

                    dp[i][nextNum] += bf;
                    dp[i][nextNum] %= MOD;
                }
            }
        }
        System.out.println(dp[m-1][0]);
    }
}