[백준] 10844 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

2021-01-09

---

import java.util.Scanner;
 
public class Main10844 {
    public static int N, dp[][];
    public static void solve() {
        for(int i = 1; i <= 9; i++) dp[1][i] = 1;
        
        for(int i = 2; i <= 100; i++) {
            dp[i][0] = dp[i-1][1];
            for(int j = 1; j <= 8; j++) {
                dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1]) % 1000000000;
            }
            dp[i][9] = dp[i-1][8] % 1000000000;
        } 
    }
    
    public static void main(String[] args) {
        dp = new int[101][10];
        solve();
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        long sum = 0;
        for(int i = 0; i <= 9; i++) sum += dp[N][i];
        System.out.println(sum % 1000000000);
    }
}
 

 

void2017.tistory.com/119

[백준] 11057 오르막 수

위의 문제와 유사하다고 생각했고, 비슷하게 풀었다.

 

#문제풀이

1. dp[][] 2차원 배열을 만든다. 첫번째 자리는 계단 수의 길이로 보고, 두번째 자리는 끝 자리 수로 보았다.

 

2. 포인트는 숫자를 크게 3종류로 나눌 수 있는데, 끝자리 수를 기준으로 계단 수를 만들 수 있는 경우의 수에 따라 나눈 것이다.

 

0 : 0과 계단 수가 될 수 있는 수는 +1인 1밖에 없다.

dp[N][0] = dp[N-1][1];

 

1 ~ 8 : 1 ~ 8까지는 -1, +1 둘 다 계단 수가 될 수 있다.

dp[N][i] = dp[N-1][i+1] + dp[N-1][i-1];

 

9 : 9와 계단 수가 될 수 있는 수는 -1인 8밖에 없다.

dp[N][9] = dp[N-1][8];