[BOJ#10844] 쉬운 계단 수(Python)

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

 

문제가 짧아서 좋았던 문제.

이동은 한층씩, 위 아래 2가지 방향으로만 가능하다.

0으로 시작하는 계단수는 없지만 0을 무시하면 안되는게 킥이었다.

층를 j로 생각한다면 이전 자릿수의 위(j+1), 아래(j-1)의 경우의 수를 더해주는 방식으로 생각했다.

ex) n = 4일때, 3의 높이의 계단에서의 경우의 수는 n = 3일 때, 높이 2의 계단수+ 높이 4의 계단수

마지막에 n의 자리수의 0을 제외한 모든 경우의 수를 더해주면 된다.

 

점화식 찾기 도식화

 

코드

N = int(input())

# dp초기화
dp = [[-1] * 10 for _ in range(N)]

# n = 1일 때, 값 넣어주기
for j in range(10):
    dp[0][j] = 1

for i in range(1, N):
    prev = [-1] * 10
    for j in range(10):
        if j == 0:
            prev[j] = dp[i-1][j+1]
        elif j == 9:
            prev[j] = dp[i-1][j-1]
        else:
            prev[j] = dp[i-1][j-1] + dp[i-1][j+1]
    
    for j in range(10):
        dp[i][j] = prev[j]

result = sum(dp[N-1][1:10]) % 1000000000
print(result)

 

이전 문제에서 누적합으로 최적화를 했던게 기억나서 prev를 썼는데,

이 문제에서는 앞, 뒤 두개씩만 연산하기 때문에 N이 커져도 성능에는 큰 차이가 없어서 안써도 될 것 같다. (메모리만먹음)

문제와 궁금증 모두해결 끝.