[백준] 10844 - 쉬운 계단수

아이데이션

처음엔 너무 쉽게 2n - 1로 풀었으나, 틀렸습니다!!의 연속이었다.

곰곰히 생각해보니까, 이건 저런 단순한 수식이 아니라
2차원 DP로 풀어야 하는 문제인 것 같았다.

n자리 수에 0 ~ 9의 숫자를 잘 넣으면 되는 문제이고,
n자리에 넣을 숫자는 n - 1자리의 숫자의 영향을 받으니까 관계도 확실했다.

아래 풀이를 보자

사진에서 새로는 0 ~ 9까지 들어갈 수 있는 숫자이고,
가로는 n자리수를 의미한다.

 

어떤 자릿수에 0이 들어갈 수 있는 경우의 수는
앞 숫자가 1인 경우 하나 밖에 없다.

1 ~ 8가 들어갈 수 있는 경우의 수는
앞이 현 숫자보다 1 작거나, 1 큰 경우의 수의 합이다.

예를 들어서, 현재 숫자가 8이면
앞 숫자가 9이거나 7이어야 되므로 두 경우의 수를 더해주면 된다.

그림으로 나타내면 위 브이자 형광펜처럼 된다!!

 

숫자가 9인 경우는 앞 숫자가 8인 경우의 수가 가능하므로,
8인 경우의 수를 그대로 이어 받으면 된다!!

 

전체적으로 관계를 표시하면 예쁜 그물망이 나온다ㅎㅎ

 

풀이

 

n = int(input())
cache = [[0] * 10 for _ in range(n + 1)]

for i in range(1, 10, 1):
    cache[1][i] = 1

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

print(sum(cache[n]) % 1000000000)