[백준, S1, DP] 쉬운 계단 수

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int size = 0;
		if (N == 1)
			size = 3;
		else
			size = N + 1;
		long[][] dp = new long[N + 1][10];
		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}

		for (int i = 1; i < N; i++) {
			for (int j = 0; j <= 9; j++) {
				if (dp[i][j] != 0) {
					if (j == 0) {
						dp[i + 1][j + 1] = +dp[i][j];
						dp[i + 1][j + 1] %= 1000000000;
					} else if (j == 9) {
						dp[i + 1][j - 1] += dp[i][j];
						dp[i + 1][j - 1] %= 1000000000;
					} else {
						dp[i + 1][j - 1] += dp[i][j];
						dp[i + 1][j + 1] += dp[i][j];
						dp[i + 1][j - 1] %= 1000000000;
						dp[i + 1][j + 1] %= 1000000000;
					}
				}
			}
		}
		int answer = 0;
		for (int i = 0; i < 10; i++) {
			answer += dp[N][i];
			answer %= 1000000000;
		}
		System.out.println(answer);
	}
}

0. 문제 링크

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

10844번: 쉬운 계단 수

---

1. 문제 핵심

1. 45656처럼 앞, 뒤 두 수의 차이가 1인 계단 수가 N자리수마다 몇 개 있는지 계산하는 문제입니다.

---

2. 문제 접근

1. DP 문제인 만큼 개수 자체에 규칙이 있을 것 같아서 1~6자리 수까지 수를 계산해보았는데 규칙성을 찾을 수 없어서 3시간 동안 고민을 했습니다.
2. 그와중에 끝이 0으로 끝나는 수는 이후 1로 끝나는 계단 1개가 있고 9로 끝나면 8로 끝나는 계단 1개가 있으며 그 외에는 위, 아래로 계단이 1개씩 있는 것은 파악했지만 이것을 어떻게 이용할지 몰랐습니다.
3. 솔루션을 보고 그 규칙을 그대로 문제에 적용하면 된다는 것을 알았습니다.
4. DP문제는 답을 알고나면 매우 간단하다는 것을 알게 되는 것을 보면 넌센스 문제를 푸는 것 같다는 생각이 들었습니다.

---

3. 코드 분석

1.  

N을 입력받고 1자리 수는 0을 제외하고 1씩 저장해 초기화를 합니다.

이전 자리의 해당 숫자 개수만큼 dp에 저장

N이 커질수록 dp에 저장되는 값 자체도 매우 커지기 때문에 항상 10억으로 나머지 값을 계산해주어야 합니다.

---

4. 베스트 코드 분석

---

5. 코드