PS/BOJ
10844
easy16
2022. 4. 24. 12:55
쉬운 계단 수,
점화식 :
1. dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] // 1~8
2. dp[i][0] = dp[i-1][1] // 0
3. dp[i][9] = dp[i-1][8] // 9
ex)
N=1인 경우, 각 자리를 만들 수 있는 경우의 수는 모두 1
dp[2][3]의 의미(3X인 경우) : 2번째 자리가 3인 경우의 수 = 첫째자리에 2,4가 올수 있는 경우의 수의 합
:32/ 34
이를 수식으로 풀면? dp[2][3]=dp[1][2] + dp[1][4]
dp[1][2] = 1 , dp[1][4] =1
Top-Down 방식 recursion : 탑다운의 표현 방식을 이해, 구하는 값을 Top -> Down 방향으로 탐색하면서 dp값을 채워나가게 된다.
Bottom-Up 방식 : recursion을 쓰지 않고, 루프를 통해 N번째 dp까지 모두 채우는 방식
import java.util.Scanner;
class Main {
static Long[][] dp;
static int N;
final static long MOD = 1000000000L;
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
dp = new Long[N + 1][10];
for (int i = 0; i < 10; ++i)
dp[1][i] = 1L;
long result = 0;
/*
* Top-Down : recursion
* for (int i = 1; i <= 9; ++i) {
* result += recur(N, i);
* }
*/
for (int i = 2; i <= N; ++i) {
for ( int j = 0; j < 10; ++j ) {
if (j == 0)
dp[i][j] = dp[i - 1][1] % MOD;
else if (j == 9)
dp[i][j] = dp[i - 1][8] % MOD;
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
}
}
//N자리의 1~9까지의 합
for (int i = 1; i <= 9 ; i++) {
result += dp[N][i];
}
System.out.println(result % MOD);
}
static long recur(int digit, int val) {
if (digit == 1) {
return dp[digit][val];
}
if (dp[digit][val] == null) {
if (val == 0) {
dp[digit][val] = recur(digit - 1, 1);
} else if (val == 9) {
dp[digit][val] = recur(digit - 1, 8);
} else {
dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
}
}
return dp[digit][val] % MOD;
}
}