백준 10844 쉬운 계단 수 파이썬

백준 10844 쉬운 계단 수 풀이

접근방식

1. n자리의 수가 주어졌을 때 끝자리에 올 수 있는 수를 구합니다.
2. 예를 들어, 끝에 n이 2인 경우, 끝에 0이 올 수 있는 경우는 1가지 뿐이지만,
3. 끝에 2이 올 수 있는 경우는 (12) (32) 처럼 2가지 경우가 있습니다.

이를 표로 정리하면 다음과 같습니다.

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

1. 표를 살펴보면 끝자리에 0과 9가 오는 경우는 각각 바로 이전 리스트의
   왼쪽, 오른쪽 대각선과 같은 값을 가진다는 것을 알 수 있습니다.
2. 1부터 8은 바로 이전의 왼쪽 대각선과 오른쪽 대각선의 합을 나타냅니다.

정답코드

import sys
input = lambda: sys.stdin.readline().rstrip()

MOD = 1000000000

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

해당 문제는 실버 1레벨의 다이나믹 프로그래밍 문제였습니다.

주어진 수의 자리수 혹은 범위를 가지고 비교하는 경우, 끝에 올 수 있는 수의 갯수를

확인하면서 dp리스트를 갱신한다면 유용하다는 것을 배웠습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady