[백준 10844번] 쉬운 계단 수 (자바)

백준알고리즘 10844번 : 쉬운 계단 수 (Solved.ac 난이도 Silver1)

 

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

DP(Dynamic programming) 문제이다.

초항의 길이별 정답을 통해 규칙을 찾고, 그 규칙들로 길이 N인 계단 수를 찾을 수 있다.

규칙을 찾기위해 자리 길이가 1일때와 2일때를 계산해보았다.

N=1일때 경우의수?
1~9 까지 총 9가지(0으로 시작하는 수는 계단 수가 아님)

N=2일 경우의 수?
맨 뒤에 9가 붙는 경우(앞에 8이 있는 갯수) - 1
맨 뒤에 8이 붙는 경우 (앞에 7,9가 있는 갯수)
맨 뒤에 7이 붙는 경우 (앞에 6,8이 있는 갯수)
''   6  ''
''   5  ''
''   4  ''
''   3  ''
맨 뒤에 2가 붙는 경우 (앞에 1,3이 있는 갯수) - 2x7
1이 붙는 경우(앞에 0,2가 있는 갯수) - 1
0이 붙는 경우(앞에 1이 있는 갯수) - 1
= 1 + 2x7 + 1 + 1  = 총 17가지

이와 같이 규칙을 세우면 다음부터는 어렵지 않다.

길이 N일때의 경우의 수 =  (길이 N-1일때 끝자리가 9인 경우의 수 + 길이 N-1일때 끝자리가 8인 경우의 수 + ... + 길이 N-1일때 끝자리가 0인 경우의 수)
라는 공식을 세울 수 있기때문이다.

 

 

풀이 과정

---

1. N이 1일때와 2일때 경우의 수를 생각하면서 규칙을 발견한다.
2. N*10의 2차원 배열을 정의하고, 1행에 초기값을 입력한다.(N=1일때 경우의 수를 직접 부여)
3. 2부터 N까지 for문을 돌면서, 각 길이별 끝 숫자별 경우의 수를 입력해준다.
   arrNum[i][j] = arrNum[i - 1][j - 1] + arrNum[i - 1][j + 1] // j가 0, 9일때 제외
4. 계산시 10억으로 틈틈히 나눠주면서 값이 long 변수 길이를 넘지않도록 주의한다.
5. 길이 N일때, 맨 끝자리 수가 0~9일때의 경우의수를 더하여 정답을 출력한다.

 

 

▽ 정답 소스 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {//[Silver1] No10844 : 쉬운 계단 수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        long[][] arrNum = new long[num][10];

        for (int i = 1; i < 10; i++) {
            arrNum[0][i] = 1;
        }//첫째자리에는 0을 뺴고 다있다.

        if (num > 1) {
            for (int i = 1; i < num; i++) {
                for (int j = 0; j < 10; j++) {
                    if (j == 0) {
                        arrNum[i][j] = arrNum[i - 1][1];
                    } else if (j == 9) {
                        arrNum[i][j] = arrNum[i - 1][8];
                    } else {
                        arrNum[i][j] = (arrNum[i - 1][j - 1] + arrNum[i - 1][j + 1]) % 1000000000;
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < 10; i++) {
            ans += arrNum[num - 1][i] % 1000000000;
        }
        System.out.println(ans % 1000000000);
    }
}