Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 10844 쉬운 계단 수
백준 10844 쉬운 계단 수
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때 길이가 N인 계단 수가 총 몇개 있는지 구해보자. 0으로 시작하는 수는 계딴 수가 아니다.
입력
- 첫 번째 줄: N,
출력
정답을 1,000,000,000으로 나눈 나머지를 출력
해결 방식
dp
- 맨 뒷자리 수를 기준으로 앞에 올 수 있는 숫자의 경우의 수를 구함
- dp[자리수][앞에 올 수 있는 수]
ex) n = 2 인 경우
- 뒷자리가 0 → 앞자리로 1만 가능
- dp[i][j] = dp[i-1][j+1]
- 뒷자리가 9 → 앞자리로 8만 가능
- dp[i][j] = dp[i-1][j-1]
- 나머지 수는 2개씩 앞자리로 올 수 있음
- dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]
코드
n = int(input())
dp = [[0 for i in range(10)] for j in range(n+1)]
for i in range(1, 10):
dp[1][i] = 1
for i in range(2, n+1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i-1][1]
elif j == 9:
dp[i][j] = dp[i-1][8]
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[n]) % 1000000000)
