[BOJ] 20500 Ezreal 여눈부터 가네 ㅈㅈ

문제 링크

www.acmicpc.net/problem/20500

풀이

단순한 DP 문제이다.
$dp[i][j] =$ $i$자리 수를 15로 나눈 나머지가 $j$인 경우의 수라고 정의하고 풀면 된다.

Java 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[][] dp = new int[1516][15];
        dp[1][1] = dp[1][5] = 1;

        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < 15; ++j) {
                dp[i + 1][(j * 10 + 1) % 15] = (dp[i + 1][(j * 10 + 1) % 15] + dp[i][j]) % 1000000007;
                dp[i + 1][(j * 10 + 5) % 15] = (dp[i + 1][(j * 10 + 5) % 15] + dp[i][j]) % 1000000007;
            }
        }

        System.out.println(dp[N][0]);
    }
}