사용한 것
- 점화식을 세워 풀이하기 위한 bottom-up
풀이 방법
- 앞이 1인 경우에만 0 가능 -> dp[i][0] = dp[i - 1][1]
- 앞이 8인 경우에만 9 가능 -> dp[i][9] = dp[i - 1][8]
- 1 ~ 8 의 경우 2를 예를들면 앞이 1이거나 3이면 가능 -> dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
코드
public class Main {
private static final int MOD = 1_000_000_000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[][] dp = new long[n + 1][10];
for (int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
switch (j) {
case 0:
dp[i][j] = dp[i - 1][1] % MOD;
break;
case 9:
dp[i][j] = dp[i - 1][8] % MOD;
break;
default:
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
break;
}
}
}
long answer = 0;
for (int i = 0; i < 10; i++) {
answer = (answer + dp[n][i]) % MOD;
}
System.out.println(answer);
}
}