[Baekjoon] 10844. 쉬운 계단 수

쉬운 계단 수

문제 설명

---

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

문제 풀이

---

# 다이나믹 프로그래밍

이 문제에서는 어떻게 하위 문제를 이용하여 상위 문제를 구했을까요?

dp 배열의 인덱스와 값으로 무엇을 설정했을까요?

N = int(input())
cnts = [[0]*10,[1]*10] + [[0 for _ in range(10)] for _ in range(N-1)]
for i in range(2,N+1):
    for j in range(10):
        if j == 0: cnts[i][j] = cnts[i-1][j+1]
        elif j == 9: cnts[i][j] = cnts[i-1][j-1]
        else: cnts[i][j] = (cnts[i-1][j-1]+cnts[i-1][j+1])%(10**9)
print(sum(cnts[N][1:])%(10**9))

dp 배열은 이차원 리스트입니다.

• 바깥 리스트의 인덱스는 자릿수를 나타냅니다.
• 안쪽 리스트의 인덱스는 맨 앞자리 수를 나타냅니다.
• 값은 해당 자릿수의 맨 앞자리 수를 가진 계단 수의 개수를 나타냅니다.

예를 들어, 3자릿수 숫자 중 맨 앞자리수가 4인 계단수의 개수는 cnts[3][4] = 4 로 나타낼 수 있습니다.

여기서 주의해야 할 것은 각 리스트의 0번째 원소도 0이 아닌 값을 갖는다는 것입니다. (cnts[3] [0] = 2 != 0)

이는 3자리 숫자의 경우 맨 앞자리 수가 0이 되지는 못하지만, 4자리 숫자의 맨 앞자리 다음 수가 0으로 시작할 수는 있기 때문입니다.

이렇게 동적 계획법을 사용하기 위하여 각 원소의 0번째 인덱스의 값도 저장합니다.

계단수에 맞게, 상위 문제는 1 차이나는 하위 문제들의 합으로 구합니다. 0번째, 9번째 원소의 경우 각각 아래, 위 원소가 없기 때문에 1 차이나는 하나의 하위 문제 값을 가져옵니다.

최종적으로, 답은 N번째 dp배열의 1~9번째 원소 값들을 모두 더한 값이 됩니다.