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

• 동적 계획법을 이용해 계단 수를 구하는 문제
  https://www.acmicpc.net/problem/10844

1. 문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

2. 문제 접근

1) 첫째 줄에 계단 수의 길이 N을 입력받는다.
2) 자리 수가 1일 때는 1부터 9까지 한개씩이기 때문에 0~9를 인덱스로 가지는 int형 배열에 1부터 9까지 인덱스의 value를 1로 정한다.
3) 자리 수 만큼 반복하면서 끝 수의 위 아래 수의 인덱스에 기존의 값들을 더해주고 마지막에 기존에 있던 수들을 빼주는 형식으로 계단 수를 구할 수 있다.

3. 코드

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

public class Main {
    static int last[] = new int[10];
    static int pre[] = new int[10];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i=1;i<10;i++){
            last[i]++;
            pre[i]++;
        }
        for(int i=2;i<=N;i++){
            for(int j=0;j<10;j++){
                if(j>0){
                    pre[j] += last[j-1];
                }
                if(j<9){
                    pre[j] += last[j+1];
                }
            }
            for(int j=0;j<10;j++){
                pre[j] -= last[j];
                pre[j] %= 1000000000;
                last[j] = pre[j];
            }
        }
        int result = 0;
        for(int i=0;i<10;i++){
            result += last[i];
            result %= 1000000000;
        }
        System.out.println(result);
    }
}