백준 10844 (Python 파이썬)

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

10844번: 쉬운 계단 수

 

실버 1 문제다. 사실 실버 1이랍시고, 그냥 이 전에 있던 dp 문제들과 별반 다를 바 없었다. 저번 문제랑 굉장히 유사해서인지 구선생님의 도움 없이 혼자서 문제를 해결할 수 있었다. 이 문제 역시 2 자릿수던지, 3 자릿수던지 모두 이전 자리에 영향을 미친다. 어떻게 미치는지는 표로 알아보도록 하자.

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1

우선 각각의 숫자로 만들 수 있는 1자리 수의 계단 수를 표로 나타낸 것이다. 1,2,3,4,5,6,7,8,9 모두 계단 수 이기 때문에 표에 1을 채워 넣을 수 있다. 2자리를 살펴보자. 2자리에서 만들 수 있는 계단 수는 10,12,23,21,34,32,45,43,56,54,67,65,78,76,89,87,98 총 17가지이다. 위의 숫자들을 바탕으로 어느 숫자부터 시작하는지를 표에 채워 넣어 보자.

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1
0	2	2	2	2	2	2	2	2	1

표가 위처럼 채워지는 것을 확인할 수 있다. 1로 시작하는 것은 10,12 2개. 2로 시작하는 것은 23,21 2개이기 때문에 표가 위처럼 완성될 수 있다. 2자리부터 계단수를 만들 때 어떻게 만들어지는 지를 잘 살펴보아야 한다. 1로 시작하는 10,12는 각각 0과 2가 붙은 수이다. 2로 시작하는 21,23 역시 1과 3이 붙은 수이다. 이전 인덱스의 옆항들이 더해져서 해당 인덱스의 항을 만드는 것을 알아볼 수 있다. 사실 여기까지 하고 점화식을 짠 뒤 코드를 짜도 무방하지만, 확실한 확인을 위해서 3자리까지 한번 확인을 해보자.

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1
0	2	2	2	2	2	2	2	2	1
0	3	4	4	4	4	4	4	3	2

1을 제외한 나머지 모든 항들이 생각한 가정에 부합하는 것을 확인할 수 있다. 사실 0도 0으로 시작하는 것이 없을 뿐이지 1 뒤에는 붙을 수 있기 때문에 9처럼 숫자를 넣어주면 된다. 위 가정들로 점화식을 짜 보면 0과 9를 제외하면

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

위를 성립하는 것을 알 수 있다.

import sys
n = int(sys.stdin.readline())
dp = [[0]*10 for i in range(n)]
dp[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(1, n):
    dp[i][0] = dp[i-1][1]
    dp[i][9] = dp[i-1][8]
    for j in range(1, 9):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print((sum(dp[n-1])-dp[n-1][0]) % 1000000000)

dp [0]만 정의해주고 정해진 자릿수까지 for문을 돌려주면 답을 구할 수 있다. dp를 조금 이해하고 있다는 생각이 들어 뿌듯하다.