[백준 10844번] 쉬운 계단 수 문제풀이 (with Python)

 

 

< 문제 >

 

 

 

< 입출력 >

 

 

 

< 풀이 >

dp 배열을 2차원 리스트로 정의해서, 자리수에 대한 정보를 dp에 넣는 새로운 문제였다.

감이 잘 잡히지 않아 소스를 참고해서 풀었다.

 

dp[자리수][앞 자리의 수] 값은 가능한 경우의 수이다. 

 

1) 앞 자리가 0인 경우,

    dp[ i ][ j ] = dp[ i - 1 ][ 1 ]

 

2) 앞 자리가 1~8인 경우,

   dp[ i ][ j ] = dp[ i -1 ][ j -1] + dp[ i -1 ][ j +1]

 

3) 앞 자리가 9인 경우, 

   dp[ i ][ j ] = dp[ i -1 ][ 8 ]

 

 

 

< 코드 >

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1


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

print(sum(dp[N]) % 1000000000)

 

 

 

 

 

 

골드 1인 BOJ 1562번 계단 수 문제도 풀어봐야겠다....!