%2022. 2. 3. 21:40에 작성된 글입니다%
20500번: Ezreal 여눈부터 가네 ㅈㅈ
문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
www.acmicpc.net
DP 문제
15의 배수이려면 5의 배수이면서 3의 배수여야 한다. 어떤 자연수 \(N\)에 대하여,
\(5\mid N \iff N\mod 10 = 0\ or\ 5\), \(3\mid N \iff 3\mid DigitSum(N)\)
만들어야 하는 수는 1과 5로만 구성되어야 하므로 첫째 자리는 무조건 5다. 이후에는 DP 배열을 만들어서 채워나가는데, \(DP[N][m]\) = 길이가 \(N\)이고 (모든 자리의 수의 합) \(\equiv m\mod 3\)인 수들의 갯수로 두어 1 혹은 5를 더해나가면 된다.