1.
테이블 정의
•
D[i][j] → 길이가 i 이고, j 로 끝나는 수의 계단 수의 개수
2.
점화식 찾기
•
길이가 i 이고, j = 0 으로 시작하는 수 일때
◦
dp[i][j] = dp[i - 1][j + 1]
•
길이가 i 이고, j = 1~8 로 시작하는 수 일때
◦
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
•
길이가 i 이고, j = 9 로 시작하는 수 일때
◦
dp[i][j] = dp[i - 1][j + 1]
3.
초기값 정하기
long[][] dp = new long[n + 1][10];
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1;
}
Java
복사
for i in range(1, 10):
dp[1][i] = 1
Python
복사
Python
num = int(input())
arr = [[0] * 10 for _ in range(num + 1)]
sum = 0
mod = 1000000000
int(sum)
int(mod)
for i in range(1, 10):
arr[1][i] = 1
for i in range(2, num+1):
for j in range(0, 10):
if (j == 0):
arr[i][j] = (arr[i-1][j+1]) % mod
elif (j >= 1 and j <= 8 ):
arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % mod
elif (j == 9):
arr[i][j] = (arr[i-1][j-1]) % mod
for i in range(0, 10):
sum += arr[num][i]
print(sum % mod)
Python
복사
JAVA
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
long[][] arr = new long[num+1][10];
long mod = 1_000_000_000;
for (int i = 1; i <= 9; i++) {
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 0) {
arr[i][j] = (arr[i-1][j+1]) % mod;
}
else if (j >= 1 && j <= 8) {
arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % mod;
}
else if (j == 9) {
arr[i][j] = (arr[i-1][j-1]) % mod;
}
}
}
long sum = 0;
for (int i = 0; i <= 9; i++) {
sum += arr[num][i];
}
System.out.println(sum % mod);
}
}
Java
복사