[Baekjoon] 10844_쉬운 계단 수

문제(출처: https://www.acmicpc.net/problem/10844)

---

< 쉬운 계단 수 >

 

문제 풀이 

 

자릿수가 늘어날수록 이전 자릿수의 상태를 이용할 수 있으므로 DP 사용한다.

 

my solution (Java)

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

public class _10844_ { // 쉬운 계단 수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		int dp[][] = new int[n + 1][10];

		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}

		for (int i = 2; i < n + 1; i++) {
			for (int j = 0; j < 10; j++) {
				if (j != 9) {
					dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % 1000000000;
				}
				if (j != 0) {
					dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % 1000000000;
				}
			}
		}

		int result = 0;
		for (int i = 0; i < 10; i++) {
			result = (result + dp[n][i]) % 1000000000;
		}
		System.out.println(result);
	}
}

변수)
n : 입력값 
dp : 1~N인 계단 수
result : 길이가 N인 계단 수 

 

n을 입력받는다. 1 자릿수일 때는 각 경우의 수가 1개이므로 dp[1][1~9]를 1로 초기화한다. 다음 자릿수부터는 현재 값의 -1, +1에 해당하는 값을 더해야 한다. 이때, 0과 9일 때를 주의한다.  

 

최종 dp[n][0~9] 값을 더해 출력한다. 

---

---