백준 20500번: Ezreal 여눈부터 가네 ㅈㅈ

문제: https://www.acmicpc.net/problem/20500

문제 풀이

DP

dp[i][j] = 1과 5로 구성되고 끝의 자리가 5인 i자리 양의 정수 중 3으로 나눈 나머지가 j인 수의 개수

15는 3과 5의 공배수이므로 15의 배수는 3의 배수, 5의 배수의 특징을 모두 가져야 함

5의 배수는 끝자리가 5, 0이고 현재 수는 1, 5만 써야 하므로 끝자리가 항상 5여야 함

3의 배수는 모든 자리수의 합이 3으로 나누어 떨어져야 함

끝의 자리수를 5로 고정하면 자릿수가 늘어날때마다 앞의 자리에 1 또는 5가 붙기 때문에 모든 자릿수의 합이 1 또는 2가 늘어남

따라서 다음과 같은 점화식이 나옴

dp[i][0] = dp[i - 1][2] + dp[i - 1][1]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][1] + dp[i - 1][0]

점화식에 맞게 dp[N][0]을 구하면 1과 5로만 구성된 $N$자리 양의 정수 중 끝 자리가 5이고 모든 자릿수의 합이 3으로 나누어 떨어지는 15의 배수의 개수가 되므로 출력하면 정답

풀이 설명

0으로 시작하지 않고 1과 5로만 구성된 $N$자리 양의 정수 중에서, 15의 배수가 몇 개인지 구하는 문제이다.

여기서 15의 배수는 3과 5의 공배수이므로 5의 배수의 성질과 3의 배수의 성질을 동시에 가져야 한다. 5의 배수의 성질은 끝 자리가 5 또는 0이라는 것이고, 3의 배수의 성질은 모든 자릿수의 합이 3으로 나누어 떨어져야 한다는 점이다.

따라서 끝 자리의 수를 5로 고정하면 앞의 자릿수가 늘어날 때마다 이전에 확인했던 수의 맨 앞에 1 또는 5를 붙이는 것이고 각각 자릿수의 합을 3으로 나눈 나머지가 1, 2씩 늘어나게 되는 것이므로 자릿수마다 3으로 나눈 나머지에 따라 끝 자리가 5인 수의 갯수를 세놓으면 다음 자릿수의 수의 갯수도 셀 수 있다.

따라서 dp[i][j]를 끝자리의 수가 5인 1과 5로만 구성된 i자리 양의 정수 중 모든 자릿수의 합을 3으로 나눈 나머지가 j인 수의 개수로 정의하면 다음 점화식이 성립한다.

dp[i][0] = dp[i - 1][2] + dp[i - 1][1]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][1] + dp[i - 1][0]

정의에 따라 dp[N][0]이 끝자리의 수가 5이고 1과 5로만 구성된 N자리 양의 정수 중 모든 자릿수의 합이 3으로 나누어 떨어지는 수이므로 15의 배수인 N자리 수가 되므로 이 값이 구하는 값이 된다. 따라서 dp[N][0]을 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    nextToken()
    val N = nval.toInt()
    val mod = 1_000_000_007
    val dp = Array(N + 1){IntArray(3)}
    dp[1][2] = 1
    for(i in 2..N){
        dp[i][0] = (dp[i - 1][2] + dp[i - 1][1]) % mod
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][0]) % mod
    }
    println(dp[N][0])
}