import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
br.close();
long f[][] = new long[N+1][10];
for(int i=1;i<=9;i++) {
f[1][i] = 1;
}
for(int i=2;i<=N;i++) {
for(int j=0;j<10;j++) {
if(j==0) {
f[i][j] = f[i-1][j+1] % 1000000000;
} else if (j==9) {
f[i][j] = f[i-1][j-1] % 1000000000;
} else {
f[i][j] = (f[i-1][j-1] + f[i-1][j+1]) % 1000000000;
}
}
}
long sum = 0;
for(int i=0;i<10;i++) {
sum += f[N][i];
}
System.out.println(sum%1000000000);
}
}
이중 배열을 활용한 DP 문제 였다.
규칙을 찾아서, 그것을 DP로 어떻게 해결할지 방법을 찾아야 한다.
이번 문제같은 경우도 각 자리가 1씩 차이나는 계단수의 특성
을 활용해서 💡끝자리
를 기준으로 삼아 이중배열을 만든다는 생각💡이 중요했다.
혼자서는 감이 오질 않아서 다른 사람들의 풀이를 참고했고, 코딩을 했는데 계속 틀렸습니다 가 뜨길래 왜 그런가 봤더니 마지막 sum % 1000000000
를 안해주었기 때문이었다.
백준 문제들에서 왜 자꾸 값을 주어진 수로 나눈 나머지를 출력하라는지는 아직 의문이다. 자료형의 범위를 벗어나는 것도 아닌데..