[백준]10844 쉬운 계단 파이썬 python

문제링크

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

코드

import sys
input = sys.stdin.readline
 
n = int(input())
 
d = [[0]*10 for _ in range(101)]
d[1] = [0,1,1,1,1,1,1,1,1,1]
for i in range(2,n+1):
    for j in range(0,10):
        if j ==0:
            d[i][j] = d[i-1][j+1]
        elif j==9:
            d[i][j] = d[i-1][j-1]
        else:
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
 
print( sum(d[n])%1000000000 )

 

POINT

- DP로 접근

- 풀이방법:

1 차이 나는 수를 연속으로 배치하기 위해서 마지막 수를 저장하고 있어야 한다. 

n번째에서 할 수 있는 행동: +0, +1, +2, ... ,+9 추가하기

단 이때, 직전 숫자가 지금 추가할 수와 1 차이가 날 때에만 해당 수를 추가할 수 있다. (by 문제의 '계단수' 정의)

 

이를 구현하기 위해서 2차원 배열 d[i][j] 생성

d[i][j] = '총 길이가 i이고 맨 마지막 수가 j인 계단수 갯수' 라고 정의 

ex) d[2][3] : 총 길이 2이고, 맨 마지막 수가 3인 계단 수 갯수  --> {2,3}, {4,3} 가 가능하므로, d[2][3]=2

 

d[i][j] = d[i-1][j-1] + d[i-1][j+1]와 같은 방식으로 저장해나간다.

단, 마지막 수(=j) 가 0일 때, j-1 = 0-1=-1 이므로 배제하고,

마지막 수가 9 일 때에는 j+1 = 9+1 =10 이 되므로 이 경우도 제외한다.