백준 : 쉬운 계단 수 [파이썬, DP]

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

10844번: 쉬운 계단 수

 

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력

1

예제 출력 

9

 

[문제 풀이]

점화식과 2차원 DP 테이블을 사용해 문제를 해결한다.

dp[자릿수][해당 자릿수에서 가장 뒤에 오는 숫자] = 경우의 수​

 

주어진 N에 따라 계단식을 구한다.

먼저 N=1 경우에, 계단 수는 무조건 1~9로 9개이다.

 

N=2인 경우에는 조금 더 복잡해진다.

N=1인 계단수의 1~9 뒤에 올 수 있는 수를 생각해보면 N=2인 경우의 계단 수를 구할 수 있다.

1~8의 경우 :  각각 +1 -1을 더한 수 10,12 ~ 87,89까지 수가 올 수 있다.
9인 경우 : 8밖에 못온다.

 

N=3인 경우에도 비슷하지만 하나의 경우가 더 추가된다.

N=2인 계단 수 뒤에 올 수 있는 수로 0의 경우가 있다.

0의 경우 마지막 수로는 1밖에 올 수 없다.

 

이제 점화식을 만들어보자.

 

예시로 마지막 3의 자리 수로 2를 넣는다고 해보자.  >> xx2

그럼 2의 자리수에는 1과 3이 올 수 있다. >> x12, x32

 

아래와 같이 표현할 수 있다.

3의 자리수에 2를 넣는 경우의 수 = 2의 자리수에 1이 오는 경우의 수 + 2의 자리수에 3이오는 경우의 수

 

식으로 바꿔보자.

dp[자릿수][가장 뒤에 오는 숫자] = dp[자릿수 - 1][가장 뒤에 오는 숫자 - 1] + dp[자릿수 - 1][가장 뒤에 오는 숫자 + 1]

이 점화식은 가장 뒤에 오는 수가 1~8될 때이다.

 

점화식은 위의 식을 포함하여 총 3가지로 분류된다.

 

가장 뒤에 오는 숫자 = 0

dp[자릿수][0] = dp[자릿수 - 1][1]

0의 앞에는 1만 올 수 있음.

 

가장 뒤에 오는 숫자 = 9

dp[자릿수][9] = dp[자릿수 - 1][8]

9의 앞에는 8만 올 수 있음

 

N=3일때의 DP 테이블은 다음과 같다.

	 각 자릿수에서 가장 뒤에 오는 숫자(0~9)
            0  1  2  3  4  5  6  7  8  9
  자릿수(0)   0  0  0  0  0  0  0  0  0  0
  자릿수(1)   0  1  1  1  1  1  1  1  1  1
  자릿수(2)   1  1  2  2  2  2  2  2  2  1
  자릿수(3)   1  3  3  4  4  4  4  4  3  2

 

[정답 코드]

위의 점화식을 활용하여 코드를 작성한다.

n = int(input())

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

MOD = 1000000000

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])%MOD)