📚 10844 - 쉬운 계단 수

쉬운 계단 수
기존 나의 코드

# 쉬운 계단 수
n = int(input())

INF = 1000000000

dp = [[0] * 10 for _ in range(n + 1)]

for idx in range(1, n + 1):
    if idx == 1:
        for in_idx in range(1, 10):
            dp[idx][in_idx] = 1
    elif idx == 2:
        for in_idx in range(1, 9):
            dp[idx][in_idx] = 2
        dp[idx][9] = 1
    else:
        for in_idx in range(1, 10):
            if in_idx == 1:
                dp[idx][1] = (dp[idx-2][1] + dp[idx-1][2]) % INF
            elif in_idx == 9:
                dp[idx][9] = (dp[idx-2][9] + dp[idx-2][7]) % INF
            else:
                dp[idx][in_idx] = (dp[idx - 1][in_idx - 1] + dp[idx - 1][in_idx + 1]) % INF

result = 0

for idx in range(1, 10):
    result += dp[n][idx]
    result %= INF

print(result)

상위권 효율적인 코드

# 쉬운 계단 수
n = int(input())

INF = 1000000000

dp = [[0] * 10 for _ in range(n + 1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]
    print(dp[i])
result = 0

for idx in range(0, 10):
    result += dp[n][idx]
    result %= INF

print(result)

➡️ https://www.acmicpc.net/source/17767811