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

문제

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

풀이

• 나머지 연산은 곱과 합이 성립한다.
• N자리 모든 수들의 나머지는 0~14이다.
• number(n)을 어떤 1과 5로만 이루어진 n자리 자릿수 중 하나라고 하자.
• 숫자가 1과 5만 올 수 있다는 것은
  • 10^(n) + number(n) (1을 맨 앞에 붙힘)
  • 5*10^(n) + number(n) (5을 맨 앞에 붙힘)
    • n + 1 자릿수는 이 두개의 수가 올 수 있다는 것이다.
    • 나머지 연산은 곱과 합이 성립한다. 따라서 두 수의 나머지는
      • 10^(n) % 15 + number(n) % 15
      • 5*10^(n) % 15 + number(n) % 15
• 해당 성질에 의해 dp로 문제를 풀 수 있다.
  • dp(i,j) = dp(i,j) + dp(i-1,15 + j-10^n%15) + dp(i-1,15 + j-5*10^n%15)
  • i: 자릿수,j: 15로 나눈 나머지