[백준 10844 : PYTHON] 쉬운 계단 수

문제 풀기 : 10844번

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라.

 

0으로 시작하는 수는 없다.

문제풀이

길이가 N일 때 앞뒤로 차이가 1이 나는 숫자가 몇 개인지를 구하는 문제이다.

뒤에 있는 숫자를 기준으로 앞에 올 수 있는 숫자의 경우의 수를 구할 것이다.

자리수마다 각각의 숫자 앞에 올 수 있는 경우의 수가 다르므로 2차원 DP 테이블을 만든다.

 

dp[ N의 수 ][ N 자리 숫자일 때 해당 숫자 앞에 올 수 있는 일의 자리 수 ]

 

간단히 n = 2 자리일 경우를 먼저 보자.

0 앞에 올 수 있는 숫자는 1 밖에 없고,

9 앞에 올 수 있는 숫자는 8 밖에 없지만

그 외에 2~8까지는 ±1한 숫자 2개가 올 수 있다.

그러므로 점화식을 작성하면

 

j가 0 일 때, dp[i][j] = dp[i-1][j+1]

j가 9 일 때, dp[i][j] = dp[i-1][j-1]

j가 2~8 일 때, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

이라고 할 수 있다.

 

이 때, 유의할 점은 1자리 수일 때 초기값은 1이지만 dp[1][0]은 0으로 초기화시켜주어야 한다.

0으로는 시작할 수 없다고 했으므로.

 

전체코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0] * 10 for _ in range(n + 1)]

# 1 자리수는 0을 제외하고(조거 : 0은 앞에 올 수 없음) 1로 초기화
for i in range(1,10):
    dp[1][i] = 1

# dp[N 자리 수][N자리 숫자일 때 해당 Index 앞에 올 수 있는 일의 자리 수]
# 2 자리수부터 시작
for i in range(2, n+1): # n 자리 수
    for j in range(10): # Index
        # 뒷자리가 0일 때는 앞에 1밖에 오지 못함
        if j == 0 : dp[i][j] = dp[i-1][j+1]
        # 뒷자리가 9일 때는 앞에 8밖에 오지 못함
        elif j == 9 : dp[i][j] = dp[i-1][j-1]
        # 뒷자리가 2~8일 때는 앞에 숫자가 2개씩 올 수 있음
        else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]


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