본문 바로가기

Study/[파이썬] 백준온라인

[백준/python] 10844 : 쉬운 계단 수

- 문제

 

- 제출

각 자리에 0부터 9까지의 자연수가 올 수 있으므로, 한 row에 10개의 space가 있는 matrix를 정의한다. 

 

우선, 첫 번째 자리에는 0을 제외한 모든 수가 올 수 있으므로 matrix의 첫 번째 row에는 첫 번째 자리를 제외한 모든 자리에 1을 넣는다.

 

그다음은 3가지 경우로 나누어 생각해야 한다.

1. 0이 오는 경우

    이 경우에는 이전 숫자가 1이었다가 down 하는 경우만 존재한다. 즉, 이전 숫자가 1이 되는 경우의 수와 같다는 의미이다. 

     => cache[i][0] = cache[i-1][1]

 

2. 9가 오는 경우

     이 경우에는 이전 숫자가 8이었다가 up 하는 경우만 존재한다. 즉, 이전 숫자가 8이 되는 경우의 수와 같다는 의미이다.

     => cache[i][9] = cache[i-1][8]

 

3. 그 외의 모든 경우 (1~8)

    N의 경우, 이전 숫자가 N-1이었다가 up 하는 경우와 이전 숫자가 N+1이었다가 down 하는 경우로 나뉜다. 따라서, 이 두 경우의 수를 합한 수가 해당 숫자가 N일 때의 경우의 수라고 할 수 있다.

     => cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]

 

N = int(input())
mod = 1000000000

def stairNum(N):
    cache = [[0]*10 for _ in range(101)]
    
    for i in range(1,10):
        cache[1][i] = 1
    
    for i in range(2,N+1):
        for j in range(10):
            if j==0:
                cache[i][j] = cache[i-1][1]
            elif j==9:
                cache[i][j] = cache[i-1][8]
            else:
                cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
    
    return sum(cache[N])

print(stairNum(N)%mod)

 

'Study > [파이썬] 백준온라인' 카테고리의 다른 글

[ 백준/python ] 5585 : 거스름돈  (0) 2021.07.30
[백준/python] 9251 : LCS  (0) 2021.07.15
[백준/python] 2225: 합분해  (0) 2021.07.14
[백준/python] 11399 : ATM  (0) 2021.07.05
[백준/python] 1929 : 소수 구하기  (0) 2021.01.13