[백준 10844] 쉬운 계단 수

 

n 이 1일때 9 (1, 2, 3, 4, ..., 9)

 

n 이 2일때 17 이다.

십의 자리수가 5일때 54 혹은 56 이어야 하므로

자리수 n 이 i, 일의 자리수가 j 일때

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

위와 같은 점화식을 얻을 수 있다.

 

n이 2일때의 계단수가 17인 이유는 01 이 빠졌기 때문이다.

일의 자리수가 0일때는 제외해야 하므로 점화식에 추가해준다.

if(j == 0) dp[i][j] = dp[i-1][j+1];
else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];

 

마찬가지로 9일때도 90 같은 수는 만들 수 없으니 예외처리 한다.

 

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[0] 배열은 n이 1일때의 경우의 수를 모두 더해주면 된다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        long dp[][] = new long[n][10];
        
        for(int i=1; i<10; i++)
            dp[0][i] = 1;
        
        for(int i=1; i<n; i++) {
            for(int j=0; j<10; 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]%1000000000 + dp[i-1][j+1]%1000000000)%1000000000;
            }
        }
        long sum = 0;
        for(int i=0; i<10; i++) {
            sum += dp[n-1][i];
            sum %= 1000000000;
        }
        System.out.println(sum);
    }
}

 

(A+B)%C = ((A%C) + (B%C))%C 를 이용하여 1,000,000,000 을 넘지 않게 연산마다 처리해주었다.