백준 10844 : 쉬운 계단 수 (Java)

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

10844번: 쉬운 계단 수

 

오늘도 알고리즘!

 

쉬운 계단 수 라는 문제이다.

 

인접한 모든 자리 수의 차이가 1이 나는 수를 계단수라고 하고

 

길이가 N인 계단 수를 찾는 문제이다.

 

다이나믹 프로그래밍으로 풀 수 있는 문제이다.

 

DP 배열을 2차원의 공간으로 생각하고 

 

dp[ 길이 ] [ 0 ~ 9 ] 까지의 공간으로 반복문을 돌면서 계산해 나갈 수 있다.

 

첫번째 0을 제외한 첫 자리수에 대한 DP값은 1이다.

 

1, 2, ... , 9

 

이후 10의 자리 수 부터는 0으로 시작하는 수를 제외하곤 그 전 자리 수의 -1, +1 의 dp값을 더하면 현재 수가 된다.

 

10, 12  ... 21 23... ...........

210, 212, 232, 234

 

이대로 DP방식으로 코드를 짜준 이후

 

N번째 모든 DP값을 더하고 정해진 1,000,000,000 으로 나눈 값을 출력해주면 됩니다!

 

이차원 배열의 DP를 생각할 수 있느냐? DP적인 사고를 할 수 있느냐를 알 수 있는 문제였습니다.

 

한번씩 생각해보시고 풀어보시면 좋은 문제라고 생각합니다.

 

오늘도 알고리즘! 오늘도 코딩!

 

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

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