[Baekjoon] 25421. 조건에 맞는 정수의 개수 - python

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

25421번: 조건에 맞는 정수의 개수

문제 정보

문제 유형	난이도	걸린 시간	해결 유무
DP	실버1	1h	O

설계 방법

dp로 접근

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

dp값에 가능한 경우의 수 더해감

n번째 자리 자연수 = 이전 번째 자리 자연수보다 2이상 차이나지 않는다

각 자리 수는 0보다 크고 10보다 작음

코드

n = int(input())
dp = [[0] * 10 for _ in range(n)]

for i in range(1, 10):
    dp[0][i] = 1

for i in range(1, n):
    for j in range(1, 10):
        t = 0
        for k in range(j - 2, j + 3):
            if 0 < k < 10:
                t += dp[i - 1][k]
                t %= 987654321
        dp[i][j] = t

print(dp) # [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 3, 4, 5, 5, 5, 5, 5, 4, 3]]
ans = 0
for i in range(10):
    ans += dp[n - 1][i]
    ans %= 987654321

print(ans)

시간 복잡도

O(N)

어려웠던 점

점화식은 금방 생각했는데 구현이 생각보다 오래 걸렸음

참고 자료

https://velog.io/@zjvlzld/알고리즘-백준-25421-java-자바