[파이썬] 백준 10844 : 쉬운 계단 수 (실버1)

[파이썬] 백준 10844 : 쉬운 계단 수 (실버1)

10844번: 쉬운 계단 수

---

문제

---

풀이

0. 방향성 생각

• 0과 9를 제외하면 양 옆에서 온다. 0 9만 예외처리

 

전체코드

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

k = 10**9
for stage in range(n-1):
    for num in range(10):
        if 0<num<9:
            dp[stage+1][num] = (dp[stage][num-1] + dp[stage][num+1])%k
        elif num == 0:
            dp[stage+1][0] = dp[stage][1]%k
        else:
            dp[stage+1][9] = dp[stage][8]%k
print(sum(dp[-1])%k)

 

• 이전 stage의 인접한 숫자에서 넘어오게 테이블을 짜면 된다.

 

코멘트

.