백준 10844번 쉬운 계단 수 [JAVA]

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

 

이 문제는 쉽지 않은 문제였다 

일단 계단수란 인접한 모든 자리수의 차이가 1인 수를 말한다 

 

길이가 1인 계단수는 1,2,3,4,5,6,7,8,9 총 9개이다 

길이가 2인 계단수는 10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98 총 17개이다

 

알고리즘설계 

 

1. 여기서 눈치 챌수있는것은  0과 9는 (1-0) (8+1)의 방법으로밖에 탄생하지 않는다

왜냐하면 (-1+1), (10-1)은 가능한 경우의 수가 아니기 때문이다

반면에 나머지 수들은 +- 총 2가지 경우를 통해 탄생이 가능하다 (ex 3은 2+1 4-1을 통해 탄생한다)

 

2. dp[i][j] -> i는 계단수의 길이,  j는 계단수의 마지막 수를 의미한다 

 dp[i][j] -> 길이가 i이고 마지막 수로 j가 오는 계단수 

 

3. 따라서 dp[n+1][10] 인 배열을 만든다 

계단의 길이는 1부터 시작하므로 계단의 길이가 n이라면 인덱스로 n까지 접근할수 있어야하므로 행은 n+1이 되야하고

어떤 수의 마지막수는 0~9 총 10개가 올수 있으므로 열을 10이 되야한다

 

4. 일단 길이가 1인 계단수부터 개수를 구한다 

 

5. 이제 길이가 1인 계단수의 개수를 이용하여 길이가 2부터 n까지의 계단수의 개수를 구한다  

 

6. 길이가 i인 계단수의 마지막수가 0이 되는 경우는 길이가 i-1인 계단수의 마지막수가 1일때만 가능하므로 

길이가 i이고 마지막수가 0인 계단수의 개수 = 길이가 i-1이고 마지막수가 1인계단수의 개수

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

 

7. 길이가 i인 계단수의 마지막수가 9가 되는 경우는 길이가 i-1인 계단수의 마지막수가 8일때만 가능하므로 
길이가 i이고 마지막수가 9인 계단수의 개수 = 길이가 i-1이고 마지막수가 8인계단수의 개수

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

 

8. 나머지 경우의 수는 +,- 둘다로 접근 가능하므로 

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

 

9. 우리가 원하는 길이가 n인 계단수의 개수만 담아서 answer변수에 저장한다 

 

import java.util.*;
public class Main {
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int mod=1000000000;
        int[][]dp =new int[n+1][10]; 


        for(int i=1;i<=9;i++){
            dp[1][i]=1; 
        }


        for(int i=2;i<=n;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]=dp[i][j]%mod;
            }
        }
        long answer=0;
        for(int i=0;i<=9;i++){
            answer+=dp[n][i];
        }

        System.out.print(answer%mod);
    }
}

 

 

 

솔직히 문제에서 왜  1,000,000,000으로 나누라는지 모르겠다 

그리고 마지막에만  1,000,000,000으로 나누면 될줄알았더니 dp배열을 계산할때마다 나눠야지 정답처리가 되더라..

그리고 anwer변수는 long형으로 해줘야 되고.. 

따질게 엄청 많은 문제였다.