백준 | 10844 - 쉬운 계단 수 (python)

🪜 쉬운 계단 수

한참동안 헤맨 동적 프로그래밍 문제,, 풀고 나니까 쪼끔 허무하다.

 

 

---

✏️ 문제

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

 

---

💡 해결방법

틀리게 생각했던건 아니지만 동적 프로그래밍으로 해결하지 못하는 방법만 계속 생각했던 문제였다. 전체 합한 수를 가지고 다음 수를 어떻게 만들지 생각하며 계속 헛걸음맘 반복한 문제,, 하지만 이렇게 고민한 덕분에 다른 방법을 생각할 수 있었다.

처음부터 차례대로 마지막은 n이 1, 2, 3, 4, 5일때의 나올 수 있는 개수의 합이다. 위에는 각각 첫 자리가 1일때부터 9일때까지의 나올 수 있는 개수를 생각했었다. 이러한 개수가 어떻게 나오는지 생각해보면 구할 수 있다.

 

그래서 끝자리를 기준으로 생각을 해야했다.

예를 들어 n=1 일때는 다음과 같은 계단이 만들어진다.

1
2
3
4
5
6
7
8
9

이렇게 총 9개의 계단이 만들어지는데, 이를 다르게 생각해보면 끝자리가 1인 계단이 1개, 끝자리가 2인 계단이 1개 ••• 마지막 끝자리에 9인 계단이 1개 이렇게 총 9개의 계단이 만들어지는 것이다. 0으로 시작하는 계단은 계단수가 아니므로 만들 수 없다.

 

n=2일때도 살펴보자

10 12
21 23
32 34
43 45
54 56
65 67
76 78
87 89
98

n=1일때의 경우에 뒤에 -1과 +1을 한 각각의 숫자를 붙여 쉬운 계단 수를 만들 수 있다. 점화식의 이해를 더 쉽게 하기 위해 계단을 뒤가 아닌 앞에 붙여본다고 생각해보자.

 

10
21
12 32
23 43
34 54
45 65
56 76
67 87
78 98
89

위에서부터 차례대로 d[2][0], d[2][1], ... , d[2][9] 라고 한다면 각각의 계단은 -1과 +1한 수를 덧붙일 수 있는 경우이니까 개수의 점화식은 다음과 같이 만들 수 있다.

 

d[n][j] = d[n-1][j-1] + d[n-1][j+1]

이때 고려해야할 점은 0을 붙일때와 9를 붙일때이다. 0은 1앞에만 붙일 수 있고, 9는 8앞에만 붙일 수 있다.

즉 각각 0과 9일때의 점화식은 d[n][0] = d[n-1][1], d[n][9] = d[n-1][8]가 된다.

 

 

👩🏻‍💻 소스코드

import sys

n = int(sys.stdin.readline())
d = [[0] + [1 for _ in range(9)]] + [[0 for _ in range(10)] for _ in range(n-1)]

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

result = sum(d[n-1]) % 1000000000
print(result)

 

---

 

 

10844번: 쉬운 계단 수