[파이썬/python] 백준 - 10844 쉬운 계단 수

문제

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

---

문제 설명

1.   45656과 같이 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.
2. N이 주어질 때 길이가 N인 계단 수가 총 몇 개 있는지 구한다.
   1. 0으로 시작하는 수는 계단 수가 아니다.

 

---

풀이

만약 계단 수가 21이라면 21을 통해 만들 수 있는 세자리 계단수는 210, 212이다.

이처럼 계단 수의 맨 뒷자리를 기준으로 +1, -1을 하면 다음 수의 계단수를 구할 수 있다.

이러한 조건을 가지고 N = 1, N = 2일 때를 구해보자.

N = 1일 경우

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1

 

만들 수 있는 계단수는 1,2,3,4,5,6,7,8,9이다.

따라서 i로 끝나는 계단수의 수를 표로 표현해 보면 위 표처럼 나오는 것을 볼 수 있다.

N = 2일 경우

0	1	2	3	4	5	6	7	8	9
1	1	2	2	2	2	2	2	2	1

 

N = 1일 때 idx - 1의 값과 idx + 1의 값을 더하면 현재 N의 idx값이 나오는 것을 확인할 수 있다.

이를 통해 점화식을 세운다.

0번째와 9번째는 양 옆이 한 개씩 밖에 없으므로 N-1 계단수의 각 1번째, 8번째 인덱스의 값을 가진다.

나머지는 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이라는 점화식을 세워 값을 구한다.

 

1. dp 배열을 선언한다.
2. dp[1]의 값을 초기화한다.
3. 2부터 N+1까지의 dp 값을 구한다.
4. N번째 값을 $10^10$으로 모듈러 연산하여 값을 출력한다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N+2)]
dp[1] = [0,1,1,1,1,1,1,1,1,1]

for i in range(2,N+1):
    dp[i][0] = dp[i-1][1]
    dp[i][9] = dp[i-1][8]
    for j in range(1,9):
        dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[N])%int(1e9))

---

시간복잡도

• 총 N회 반복하므로 $O(N)$의 시간복잡도를 가진다.
• 최악의 경우 $N = 100$이므로 $O(100)$의 시간복잡도를 가진다.