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

n = int(input())
dp = [[0 for i in range(10)] for j in range(101)]

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)

언제나 dp문제는 경우의 수를 직접 메모장에 써보며 푸는 방법이 좋은 것 같다.

경우의 수를 적다보면 각 자리수에서 맨 뒤 자리에 오는 수의 개수가 규칙이 있다는 것을 알 수 있다.

이것을 표로 나타내면 아래와 같다.

 

각 자리수에서 맨 뒤 자리에 오는 수(0 ~ 9)의 개수

	0	1	2	3	4	5	6	7	8	9
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

위의 표를 보면 규칙을 한 눈에 확인할 수 있는데,

 

1 자리수인 경우를 제외하고는,

 

i를 자리수, 

j를 맨 뒤 자리에 오는 수 (0~9)라 한다면.

 

• j가 0이면 => dp[i][j] = dp[i - 1][1]
• j가 9면 => dp[i][j] = dp[i - 1][8]
• j가 1 ~ 8이면 => dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

 

위와 같은 규칙을 얻을 수 있고, 위의 식을 코드에 적용하면 답을 구할 수 있다.