백준 10844번: 쉬운 계단수 실버 1(파이썬)

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

10844번: 쉬운 계단 수

 

입력:

    입력으로 받는 N은 계단수의 길이를 의미합니다. 

 

출력:

    N의 길이를 가지는 계단수 개수를 10**9로 나눈 나머지를 출력하면 됩니다.

 

 

따라서, 1의 경우:

    1, 2, 3, 4, 5, 6, 7, 8, 9 (9가지)

 

2의 경우:

    10 , 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 (17가지)

 

풀이:

    2차원 배열을 선언합니다. d[i][j]

    i = 0 ~ N, i는 자릿수를 뜻합니다. 

    j = 0 ~ 9,  j는 자릿수에 들어갈 수 있는 숫자입니다. 

 

    d[1]의 경우, N이 1일때 각 숫자들의 개수입니다.

        [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]  ==  1, 2, 3, 4, 5, 6, 7, 8, 9 (9가지)

        0은 0개 나머지는 모두 1개이므로 총 합이 9개가 됩니다.

 

점화식:

    j == 0 인경우:

        다음 자릿수의 1에 개수를 더해주면되고

    j == 9 인경우:

        다음 자릿수의 8에 개수를 더해주면되고

    j == 1~8인경우:

        다음 자릿수의 i-1, i+1에 개수를 더해주면됩니다.

 

이를 코드로 하면,

for i in range(1, n):
    for j in range(10):
        if j == 0:
            d[i][1] += d[i-1][j]
        elif j == 9:
            d[i][8] += d[i-1][j]
        else:
            d[i][j-1] += d[i-1][j]
            d[i][j+1] += d[i-1][j]

 

 

최종코드(해당 코드에서 자릿수는 0~N-1):

# BOJ 10844 쉬운 계단 실버1
#https://www.acmicpc.net/problem/15486

n = int(input())
d = [[0 for _ in range(10)] for _ in range(n)]

# 첫번째 자릿수는 초기화해준다.
for i in range(1, 10):
    d[0][i] = 1

for i in range(1, n):
    for j in range(10):
        if j == 0:
            d[i][1] += d[i-1][j]
        elif j == 9:
            d[i][8] += d[i-1][j]
        else:
            d[i][j-1] += d[i-1][j]
            d[i][j+1] += d[i-1][j]

print(sum(d[n-1])%10**9)