boj)10844 - 쉬운 계단 수
2020. 9. 17. 15:04ㆍPS/boj
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
// # 쉬운 계단 수
public class boj_10844 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static final long mod = 1000000000L;
static long[][] dp = new long[101][10];
public static void main(String[] args) throws Exception {
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= 100; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 0) {
dp[i][j] = dp[i-1][j+1];
} else if (j == 9) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1];
}
dp[i][j] %= mod;
}
}
int n = Integer.parseInt(br.readLine());
long ans = 0;
for (int i = 0; i <= 9; i++) {
ans += dp[n][i];
}
ans %= mod;
bw.write(ans + "\n");
bw.flush();
bw.close();
}
}
- 연속된 조건 ? 이중 배열 ?
- 길이가 N일때 마지막에 올 수 있는 수는 L : 0~9
- L이 왔을때 그 앞에 오는 수는 L-1 or L+1
- DP[N][L] = DP[N-1][L-1] + DP[N-1][L+1]로 점화식을 짤 수 있다.
- L이 근데 0이나 9가 올 경우는 예외 처리가 필요하다.
'PS > boj' 카테고리의 다른 글
boj)11053 - 가장 긴 증가하는 부분 수열 (0) | 2020.09.17 |
---|---|
boj)2193 - 이친수 (0) | 2020.09.17 |
boj)15590 - 1, 2, 3 더하기 5 (0) | 2020.09.17 |
boj)16194 - 카드 구매하기 2 (0) | 2020.09.17 |
boj)11052 - 카드 구매하기 (0) | 2020.09.17 |