[백준 java] 10884 - 쉬운 계단 수

10844번: 쉬운 계단 수

---

 

문제풀이

첫째줄 n을 입력받는다. 여기서 n은 자릿수를 나타낸다

 

n=2 두자릿수 중 계단 수를 찾는다.

(총 17개)
1 :  10,  12  (2개)
2 :  21,  23  (2개)
3 :  32,  34  (2개)
4 :  43,  45  (2개)
5 :  54,  56  (2개)
6 :  65,  67  (2개)
7 :  76,  78  (2개)
8 :  87,  89  (2개)
9 :  98         (1개)

 

만약 n이 3이라면

n=3
1 :  123,  121,  101                (4개)

2 :  210,  212,  232,  234       (4개)

 

두번째 자릿수의 경우의 수는 n=2에서 구한 갯수가 들어간다.

예를들어 첫번째 자릿수가 2이면 두번째 자릿수에 올수있는 수는 1이나 3이다.

1. 빼는 경우     :  dp[i][j-1] 

2. 더하는 경우 :  dp[i][j+1] 

 

두번째 자릿수가 1일때 올수있는 수는 위에서 구한 1, 2 와 1, 0 두개이다

두번째 자릿수가 3이면  3,2와  3,4 두 개의 숫자가 올 수 있다.

 

 

예외처리

두번째 자리수가 0일때와 9일때 예외가 발생한다

왜냐하면 문제의 첫번째 자리수는 0이 올수 없으니 가져올수 있는 수가 없어서이다.

 

1. 빼는 경우

예를들어 n=3이고 첫번째 수가 1이라고 생각해보면

두번째에 올 수 있는 숫자는 0과 3이다.

2로 시작하는 n=2인 경우는 저장했지만 0으로 시작하는 수는 n=2인 경우는 없기때문에.

 

2. 더하는 경우

그리고 첫번째 수가 9가오면 두번째에 올수있는 수는 8 뿐이다.

그래서 두번째 숫자가 8일때만 계산해준다

 

 

주의사항

계산을 할때 10^9로 나눈 나머지를 더해주는 것과

마지막 정답은 10^9로 나눈 나머지를 출력하는 것을 잊지말자

---

// 쉬운 계단 수
// https://www.acmicpc.net/problem/10844
import java.util.Scanner;

public class B10844 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // dp[자릿수][두번째 숫자]
        long[][] dp = new long[101][10];
        for (int i = 1; i <10; i++) {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < 10; j++) {
                if((j-1)==0) dp[i][j] += (dp[i-2][j] % 1000000000);
                else dp[i][j] += (dp[i-1][j-1] % 1000000000);

                if( (j+1) !=10) dp[i][j] += (dp[i-1][j+1] % 1000000000);
            }
        }
        long sum = 0;
        for (int i = 1; i < 10; i++) {
            sum += dp[n][i];
        }
        System.out.println(sum%1000000000);
    }
}

한번에 성공!