[Baekjoon]백준 10844 쉬운 계단 수(실버 1) - Python

문제설명

문제를 살펴보면 계단수의 개수를 구하는 문제이다

계단수란 12321처럼 각 자릿수의 차이가 1이 나는 수이다

일단 처음에 들었던 생각으로는 재귀적 호출을 사용한 Dynamic Programming을 쓰려고 했다

이전문제에서 그런 방식으로 문제를 풀었기때문에 시도해보다가 굳이 재귀적 호출을 쓰지 않아도 되겠다는 생각이 들었다

(그러다보니 문제에서 굳이 필요없는 함수 호출을 하였다)

 

일단 하나의 간단한 for문을 통해 1자리 계단수를 초기화한다

이후 for문을 통하여 각 자리수마다의 배열을 갱신하여주면되는데, 주의할 점으로는 끝자리 수가 0이거나 9인 경우에는

더하거나 빼면 범위를 벗어나기 때문에 이 부분에 있어서는 조심하여 작성하여야한다

그리고 해당 result배열에 마지막 숫자가 j-1인 경우, j+1인 경우를 더하여 계단수를 더해준다

마지막에는 해당 배열의 합을 구하면 되는데, 문제에서 정답을 1,000,000,000으로 나눈 나머지를 출력하라고 하였으므로

그에 맞게 코드를 작성하여주면 된다

num = int(input())

def sol(n):
    result = [[0] * 10 for _ in range(n + 1)]
    
    for i in range(1, 10):
        result[1][i] = 1
        
    for i in range(2, n + 1):
        for j in range(10):
            if j > 0:
                result[i][j] += result[i - 1][j - 1]
            if j < 9:
                result[i][j] += result[i - 1][j + 1]
        
    return sum(result[n])

print(sol(num) % 1000000000)