[백준] 10844번: 쉬운 계단 수 (sol.x)

풀이시간: 20분 (틀림)

1. 나의 풀이

MOD = 1_000_000_000
N = int(input())

dp = [0] * 101
dp[1] = 9
dp[2] = 17

def is_dp(n):
    return dp[n]

def f(n):
    if is_dp(n):
        return dp[n]

    dp[n] = 2 * f(n - 1) - 2 
    return dp[n] % MOD

print(f(N))

• n = 3 부터 앞이 0이면 1개, 1~8이면 2개씩, 9이면 1개로 끝이 분기된다.
• f(n) = 2f(n-1) - 2 (n >= 3)

2. 또다른 풀이

MOD = 1_000_000_000

# cache[n][d]: 길이가 n, 마지막 숫자가 d인 계단수 개수
cache = [[0] * 10 for _ in range(101)]

for j  in range(1, 10):
    cache[1][j] = 1

for i in range(2, 101):
    for j  in range(10):
        if j > 0:
            cache[i][j] += cache[i - 1][j - 1]
            cache[i][j] %= MOD

        if j < 9:
            cache[i][j] += cache[i - 1][j + 1]
            cache[i][j] %= MOD

ans = 0
N = int(input())
for j  in range(10):
    ans += cache[N][j]
    ans %= MOD

print(ans)

• f(n, d) 길이 n이고 마지막 숫자가 d인 계단 수 총 개수
• 맨 마지막 숫자(d)가 무엇이냐에 따라 다음 숫자가 결정된다.
• (f(n, 0) + f(n, 1) + ... + f(n, 9)) % MOD
• f(n, d) = f(n + 1, d + 1) + f(n + 1, d - 1)

3. 보완할 것

• 상황을 나눌 때, 매개변수를 2개로 할 생각도 할 것
• 매개변수 2개는 2중배열로 캐싱
• 상황이 2가지 이상으로 나뉠 때, 2가지 각각 생각하자