[BOJ][Python][실3][10844] 쉬운 계단 수

문제 링크

문제링크

첫 번째 풀이

dp[i][j] : 1의 자리가 i인 길이가 j인 계단 수의 갯수

정답코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")
#
n = int(input())
R, C, K = 10, 110, 1
# dp1 = [[0] * C]
dp2 = [[0] * C for _ in range(R)]
# dp3 = [[[0] * K for _ in range(C)] for _ in range(R)]
MOD = 1000000000

for r in range(1, 10):
    dp2[r][0] = 1
for c in range(1, n):
    for r in range(0, 10):
        if r == 0:
            dp2[r][c] = dp2[1][c - 1] % MOD
        elif r == 9:
            dp2[r][c] = dp2[8][c - 1] % MOD
        else:
            dp2[r][c] = ((dp2[r - 1][c - 1] % MOD) + (dp2[r + 1][c - 1] % MOD)) % MOD

ans = 0
for r in range(0,10):
    ans += dp2[r][n-1]%MOD
ans %= MOD
print(ans)

Success Notice: 수고하셨습니다.