[java] 백준 알고리즘 10844번 쉬운 계단 수 풀이

이 문제는 이중배열을 사용해야 풀 수 있었다

이 문제를 푸는 가장 쉬운 방법은 이 문제는 이중배열을 사용해야 한다는 것과 4자릿수 정도까지 직접 써보면 된다.

4자릿수를 다 완성하기 전에 이미 규칙을 깨닫게 된다.

맨 앞자리가 1일 경우, 2번째 전 행의 앞자리 1인 계단 수 개수와 1번째 전 행의 앞자리가 2인 계단 수 개수를 합치면 된다.

맨 앞자리가 2~8은, 1행 전의 해당 열의 -1,+1열을 더한 값과 같다

맨 앞자리가 9는, 1행 전의 8열 계단 수와 같다.

** 한번 봅시다

맨 앞 자릿수	1	2	3	4	5	6	7	8	9
수의 길이: 1	1 (1)	1 (2)	1 (3)	1 (4)	1 (5)	1 (6)	1 (7)	1 (8)	1 (9)
수의 길이: 2	2 (10,12)	2 (21,23)	2 (32,34)	2 (43,45)	2 (54,56)	2 (65,67)	2 (76,78)	2 (87,89)	1 (98)
수의 길이: 3	3 (101,121,123)	4 (210,212, 232,234)	4 (321,323, 343,345)	4 (432,434, 454,456)	4 (543,545, 565,567)	4 (654,656, 676,678)	4 (765,767, 787,789)	3 (876,878, 898)	2 (987,989)

표에서 보듯이,

수의 길이가 늘어날수록, 직전 수의 길이 계단 수에 영향을 받는다

* 풀이소스

public class Baekjoon10844{
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        long[][] stairArray = new long[100][9]; // 최대 100행까지 생길 수 있음
        long result = 0;
        
        for(int i=0; i<9; i++) {
            stairArray[0][i] = 1; // 1행일 경우, 1~9까지 계단 수는 각각 1개다.
            
            /* 2자리수 배열 */
            if(i==8) { // 9에 해당하는 계단수(0부터 시작하기 때문에 8이다)
                stairArray[1][i] = 1; 
            }else {
                stairArray[1][i] = 2; // 9를 제외하고 2자리 수 계단 수는 2개씩있다.
            }
        }
        
        if(n>2) {
            for(int i=2; i<n; i++) { // 3행부터 즉, 3자리수부터 시작하는 이유는 맨 앞 1이 나올 경우, 2번째 전 행의 값을 활용하기 위해서
                
                for(int j=0; j<9; j++) {
                    
                    if(j==0) {
                        stairArray[i][j] = (stairArray[i-2][j] + stairArray[i-1][j+1])%1000000000; // 앞자리 1의 경우, 2번째 전의 행 앞자리 1값 + 1개 행 전의 앞자리 2의 값
                    }else if(j==8) {
                        stairArray[i][j] = (stairArray[i-1][j-1])%1000000000; // 앞자리가 9의 경우, 1행 전의 앞자리가 8인 계단수들이다
                    }else {
                        stairArray[i][j] = (stairArray[i-1][j-1] + stairArray[i-1][j+1])%1000000000;
                    }
                }
            }
        }
        
        for(int i=0; i<9; i++) {
            result += stairArray[n-1][i]; // 앞자리가 1~9인 계단수를 총 합치면 자릿수의 총 계단수가 나온다
        }
        bw.write(String.valueOf(result%1000000000));
        bw.flush();
        
    }
 
}