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

문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

입력

 N이 주어진다.

출력

문제의 답을 1000000007로 나눈 나머지를 출력한다.

제한

 1≤N≤1515

 

 

---

 

풀이

15의 배수는 3의 배수이면서 5의 배수인 조건과 필요충분조건이다. 그러니, 3의 배수이면서 5의 배수인 수를 찾자.

일단, 5의 배수이기 때문에 끝자리는 무조건 5로 끝난다(0은 사용 불가능함.).

그리고, N이 3의 배수이다는 N의 자릿수 합이 3의 배수인 것이랑 동치이다.

그러므로, dp: 3*(N+1) matrix을 다음과 같이 짜자:

dp[i][j]: '1과 5로만 구성된 j자리 숫자 중 3으로 나눈 나머지가 i인 수의 개수'

base case: dp[0][1] = 0, dp[1][1] = 0, dp[2][1] = 1이다. 이후 점화식은 스스로 짜보자.

j를 2부터 N까지 for문을 돌려, dp[0][N]을 구해 최종적으로 출력하면 된다.

마지막으로, 1000000007의 나머지를 출력해야하는 점도 잊지 말자.

 

---

 

코드

MAX_SIZE = 1000000007

N = int(input())
dp = [[0]*3 for _ in range(N+1)]

dp[1] = [0, 0, 1]
for i in range(2, N+1):
    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % MAX_SIZE
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MAX_SIZE
    dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % MAX_SIZE

print(dp[N][0])

 

 

P.S.

이즈 선여눈 가는게 그렇게 나쁜가?