[Python] 백준 10844번:쉬운 계단 수 / 문제 풀이, 설명

[Python] 백준 10844번:쉬운 계단 수 / 문제 풀이, 설명

---

º 코드

N = int(input())
dp = [[0,1,1,1,1,1,1,1,1,1] for _ in range(N+1)]

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

print(sum(dp[N])%10**9)

º 풀이

1. 풀이 과정

• N이 2일 때
  1. 맨 뒤에 0이 오는 경우 : 01 (1개)
  2. 1이 오는 경우 : 21 (1개)
  3. 2가 오는 경우 : 12,32 (2개)
  4. 즉 2가 올려면 앞에서 1과 3이 나와줘야한다.  

잘 봐야 하는 부분

• 알고리즘
  1. 자릿수를 i로 0~9까지 인덱스를 j로 한다면
     1. j == 0 일 때 dp[i][0] = dp[i-1][1]
     2. j == 9 일 때 dp[i][9] = dp[i-1][8]
     3. 그 외의 경우 ( 2 ~ 8 )는 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]