[Java] BOJ10844_쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

출력 조건에서 값이 매우 크기 때문에 브루트 포스로는 할 수 없다는 것을 알았고, 이전 자리까지의 수가 다음 자리의 수를 결정하기 때문에 DP라는 것을 유추할 수 있었다.

N자리 수에서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 맨 끝에 몇 개 올 수 있는지에 대하여 DP 배열을 구성했다.

주의할 점은 0은 1번째자리에서 존재할 수 없고, 이전 수는 오직 1뿐만이 가능하다. 9는 8뿐만이 가능하다. 0과 9는 서로 계단 수가 아니다.

나머지 수는 자신보다 큰 값이나 작은 값 다음에 올 수 있다.

 

*시도는 안해봤지만 자료형을 int로 하거나 매 과정에서 mod연산을 취해주지 않으면 답이 틀릴 수도 있다.

 

import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long[][] dp = new long[10][N+1];
		for (int i = 1; i < 10; i++) {
			dp[i][1] = 1;
		}
		for (int i = 2; i <= N; i++) {
			for (int j = 0; j < 10; j++) {
				if(j == 0) {
					dp[j][i] = dp[1][i-1] % 1000000000;
				} else if(j == 9) {
					dp[j][i] = dp[8][i-1] % 1000000000;
				} else {
					dp[j][i] = (dp[j-1][i-1] % 1000000000 + dp[j+1][i-1] % 1000000000) % 1000000000;
				}
			}
		}
		long res = 0;
		for (int i = 0; i < 10; i++) {
			res += dp[i][N] % 1000000000;
		}
		System.out.println(res % 1000000000);
	}

}